Stochastic series expansion

The stochastic series expansion (SSE) algorithm is a generalization of Handscomb s power-series method for the Heisenberg model. To derive an SSE representation of the partition function, we start from a Taylor expansion in powers of the inverse temperature. We then decompose the 

Hamiltonian into two or more terms H = Hj such that the matrix elements with respect to some basis can be calculated easily, giving 

Inserting complete sets of basis states between the different Hi factors then leads to a similar representation of the partition function and a similar world-line picture as in the world-line Monte Carlo method. Because there is no Trotter decomposition involved, the method is free of time discretization errors from the outset. Early applications of the SSE method employed local updates, but more efficient cluster-type updates have been developed more recently to overcome the critical slowing down. They include the operator-loop update and the previously mentioned directed-loop algorithm.  

The source code for some of the algorithms discussed above is available on the Internet as part of the ALPS (Algorithms and Libraries for Physics Simulations) project. SSE programs for the Heisenberg model can also be found on the homepage of A. Sandvik.  

---

Fig. 10. Examples of world fine configurations in (a) a path-integral representation where the time direction is continuous and (b) the stochastic series expansion (SSE) representation where the time direction is discrete. Since the SSE representation perturbs not only in offdiagonal terms but also in diagonal terms, additional diagonal terms are present in the representation, indicated by dashed lines...

In the stochastic series expansion a one-dimensional representation is sufficient to calculate properties as a function of the temperature ... 

A. Sandvik (1999) Stochastic series expansion method with operator-loop update. Phys. Rev. B 59, p. R14157... 

A. Dorneich and M. Troyer (2001) Accessing the dynamics of large many-particle systems using the stochastic series expansion. Phys. Rev. E 64, p. 066701... 

Sandvik performed quantum Monte Carlo simulations of the Heisenberg Hamiltonian on the critical infinite percolation cluster (p = pp) using the stochastic series expansion method with operator loop update. 

Internal noise is described by a master equation. When this equation cannot be solved exactly it is necessary to have a systematic approximation method - rather than the naive Fokker-Planck and Langevin approximations. Such a method will now be developed in the form of a power series expansion in a parameter Q. In lowest order it reproduces the macroscopic equation and thereby demonstrates how a deterministic equation emerges from the stochastic description. 

The stochastic dynamics usually applied in finance literature is generated by lognormal- or close-to-lognormal -distributed random variables. Leip-nik (1991) shows that the series expansion of order M of a Gog) characteristic function in terms of the cumulants diverges for M oo. Hence, the... 

Isukapalli et al. (2000) coupled the Stochastic Response Surface Method (SRSM) with ADIFOR. The ADIFOR method (see Sect. 5.2.5) is used to transform the model code into one that calculates the derivatives of the model outputs with respect to inputs or transformed inputs. The calculated model outputs and the derivatives at a set of sample points are used to approximate the unknown coefficients in the series expansions of outputs. The coupling of the SRSM and ADIFOR methods was applied for an atmospheric photochemical model. The results obtained agree closely with those of the traditional Monte Carlo and Latin hypercube sampling methods whilst reducing the required number of model simulations by about two orders of magnitude. 

In this section, the URP (updated reference-point) method proposed originally for stochastic input is explained (Fujita and Takewaki 2011a). This method can be used as an efficient uncertainty analysis to obtain the robustness function a explained in the previous section. Since the URP method takes full advantage of an approximation of first- and second-order Taylor series expansion in the interval analysis, the formulation of Taylor series expansion in the interval analysis and the achievement of second-order Taylor series expansion proposed by Chen et al. (2009) are explained briefly. 

Once the random field involved in the stochastic boundary value problem has been discretized, a solution method has to be adopted in order to solve the boundary value problem numerically. The choice of the solution method depends on the required statistical information of the solution. If only the first two statistical moments of the solution are of interest second moment analysis), the perturbafion method can be applied. However, if a. full probabilistic analysis is necessary, Galerkin schemes can be utilized or one has to resort to Monte Carlo simulations eventually in combination with a von Neumann series expansion. 

The perturbation method starts with a Taylor series expansion of the solution, the external loading, and the stochastic stiffness matrix in terms of the random variables introduced by the discretization of the random parameter field. The unknown coefficients in the expansion of the solution are obtained by equating terms of equal order in the expansion. From this, approximations of the first two statistical moments can be obtained. The perturbation method is computationally more efficient than direct Monte Carlo simulation. However, higher-order approximations will increase the computational effort dramatically, and therefore accurate results are obtained for small coefficients of variation only. 

For the SFE solution of stochastic boundary value problems, a mathematical theory is available that is in many aspects comparable to its deterministic counterpart, the finite element method. However, for random fields with short correlation lengths (requiring a high number M of random variables), the solution methods become inefficient, due to the series expansion of the solution. This is also tme for most other SFE approximations, be they global or local, and recourse to efficient sampling... 

While the explicit Euler method is simple, it is not very accurate. For a deterministic differential equation, we build higher-order methods through Taylor series expansions however, the rules of stochastic calculus are different. Consider the SDE... 

Impulse-response and transfer functions can be measured not only by pulse excitation, but also by excitation with monochromatic, continuous waves (CW), and with continuous noise or stochastic excitation. In general, the transformation executed by the system can be described by an expansion of the acquiired response signal in a series of convolutions of the impulse-response functions with different powers of the excitation [Marl, Schl]. Given the excitation and response functions, the impulse-response functions can be retrieved by deconvolution of the signals. For white noise excitation, deconvolution is equivalent to cross-correlation [Leel]. 

They differ from the kernels it (ti, ..., r ) of the Volterra series only by a faster signal decay with increasing time arguments [Bliil]. For coinciding time arguments the crosscorrelation function is the sum of the n-dimensional impulse-response function h with the impulse-response functions hm of lower orders m < n. The stochastic impulse-response functions h are the kernels of an expansion of the system response y(t) similar to the Volterra series (4.2.4) but with functionals orthogonalized for white-noise excitation x t) [Bliil, Marl, Leel, Schl], This expansion is known by the name Wiener series, and the h are referred to as Wiener kernels. 

However, the operators involved are not equivalent to the operators that would arise from any stochastic differential equation (see [403]), so we must give up the direct analogy between the formal series and continuous SDE models (which is available in the deterministic setting). Nonetheless, it is possible to analyze the resulting operator expansion in a formal way. 

According to the Karhunen-Loeve (K-L) theorem, a stochastic process on a bounded interval can be represented as an infinite linear combination of orthogonal functions, the coefficients of which constitute uncorrelated random variables. The basis functions in K-L expansions are obtained by eigendecomposition of the autocovariance function of the stochastic process and are shown to be its most optimal series representation. The deterministic basis functions, which are orthonormal, are the eigenfunctions of the autocovariance function and their magnitudes are the eigenvalues. The Karhunen-Loeve expansion converges in the mean-square sense for any distribution of the stochastic process (Papoulis and Pillai 2002). A K-L representation of a zero-mean stochastic process f(t, 6) can be represented in the form... 

Cameron RH, Martin WT (1947) The orthogonal development of nonlinear functionals in series of Fouiier-Hermite functionals. Ann Math 48 385—392 Cramer H (1966) On the intersectirais between the trajectories of a normal stationary stochastic process and a high level. Ark Math 6 337-349 Desai A, Sarkar S (2010) Analysis of a nonlinear aero-elastic system with parametric uncertainties using polynomial chaos expansion. Math Probl Eng, pages Article ID 379472. doi 10.1155/2010/379472 Evans M, Swartz T (2000) Approximating integrals via Monte Carlo and deterministic methods. Oxford University Press, Oxford... 

---