Computational Physics

10.2 Monte Carlo integration 297

exact integral. We calculate the variance in the result:

σ^2 =

〈(

b−a

N

∑N

i= 1

fi

) 2 〉

−

(〈

b−a

N

∑N

i= 1

fi

〉) 2

. (10.3)

The angular brackets denote an average over all possible realisations of the sequence
of random coordinatesxi. Carrying out this average for the last term on the right
hand side gives the square of the averagefof the functionfon[a,b]. Splitting the
sums in the first term on the right hand side into a sum withi=jand one with
i=jleads after some manipulation to

σ^2 =

(b−a)^2

N

(f^2 −f^2 ) (10.4)

where the bar denotes an average of the function on[a,b]. We see that the error is
proportional to the variance offon[a,b]. The fact thatσ∝ 1 /

√

Nis to be expec-
ted from the central limit theorem. This scaling is clearly unfavourable compared
with standard quadrature methods using equidistant values for thexi, which yields
an errorN−kwithk ≥1. However, MC integration is more efficient in higher
dimensions. To see this, let us consider standard numerical integration, with error
O(hk), for ad-dimensional integral. For simplicity we assume that the integration
volume is a hypercube with sideL. This containsN=(L/h)dpoints and therefore
the error in the result scales asN−k/d. The error of the Monte Carlo integration,
however, is independent ofd; it is stillO(N−^1 /^2 ), since the central limit theorem
does not depend on the dimension. Comparing this error with that of the standard
method, we see that MC integration is more efficient than an order-kalgorithm
whend> 2 k.
This is a rather counterintuitive result: we would expect that using a regular grid
for calculating the integral would always be superior to the random distribution of
points of the Monte Carlo method. The reason for the superiority of MC integration
in higher dimensions is that in a sense the random distribution is more homogeneous
than the regular grid. Consider for example a rectangular volume within the integ-
ration volume. A homogeneous distribution of the integration points would imply
that the number of points within this rectangular volume should be approximately
proportional to that volume. If we choose the rectangular volume to have sides
parallel to the axes of the point grid used in the standard integration method, it is
clear that on increasing the volume size, the number of points it contains increases
stepwise whenever a facet of the volume moves through an array of integration
points. In this respect random distributions are more homogeneous, since for these
distributions such steps in the number of points are extremely unlikely to occur. This
heuristic argument can be formalised – see the review by James [9] and references
therein.