Variance-Reducing Techniques

The goal of this section is to introduce a few techniques commonly used for reducting the statistical error in Monte Carlo computations of ensemble averages.

According to the previous section, the Monte Carlo computation of the ensemble average

$$\langle A \rangle = Z^{-1} \int d {\xi} A(\xi) e^{-\beta E(\xi)},$$ (339)

entails sampling an ensemble of random configurations $\xi$ with probability distribution $P(\xi)=Z^{-1}$   exp$[-\beta E(\xi)]$, computing $A(\xi)$ for each configuration and finally averaging all of these values to obtained the unbiased estimator $\bar{A}$ introduced by Eq. (338).

The convergence rate of such computation is determined by the central limit theorem (CLT) (see, e.g., K.L. Chung A course in Probability Theory, Academic Press, New York, 1974).

The CLT states that given a sequence of random variables $A(\xi_1), A(\xi_2),A(\xi_3), ... A(\xi_N)$ with expectation $\langle A \rangle$ and variance

$$\sigma^2 = \frac{1}{N} \sum_{\xi} N(\xi) (A(\xi) - \langle A \rangle)^2,$$ (340)

then the distribution of averages $\bar{A}$ obtained with different sequences of random variables tends to be a Gaussian distribution

$$G(\bar{A}) = \frac{1}{\sqrt{2 \pi} \varepsilon} e^{-\frac{(\bar{A}-\langle A \rangle)^2}{2 \varepsilon^2}},$$ (341)

where

$$\varepsilon = \sigma/\sqrt{N},$$ (342)

regardless of the dimensionality of the integral introduced by Eq. (339) and the nature of the probability function used to generate the sequences of random variables $A(\xi_1), A(\xi_2),A(\xi_3), ... A(\xi_N)$.

The standard deviation $\varepsilon$ of the distribution of the average is the standard error of the Monte Carlo computation. Therefore, results are reported as follows

$$\langle A \rangle = \bar{A} \pm \varepsilon.$$ (343)

Note that according to the definitions of the variance and the standard error, introduced by Eqs. (340) and (342), respectively, the standard error is large whenever the random variables $A(\xi_j)$ spread over a wide range of values. This is one of the main problems in calculations of high dimensional integrals, since the integrand $A(\xi)$ usually spreads over a very large range of values and the variance $\sigma^2$ is thus formidably large. In addition, depending on the observable of interest, the Boltzmann distribution might not sample the configurations of the system that contribute with the most to the ensemble average. These difficulties are sometimes overcome by implementing variance reduction techniques such as importance sampling, correlated sampling, stratified sampling, adaptive sampling, control variates and umbrella sampling. J.M. Hammersley and D.C. Handscomb Monte Carlo Methods, Chapter 5, John Wiley & Sons Inc., London, (1964) and J.S. Liu Monte Carlo Strategies in Scientific Computing, Chapter 2, Springer New York (2001) are recommended references for these methods. Here we limit our presentation to a concise description of some of them.