Monte Carlo Integration - Overview

Overview

Consider the set, subset of on which the multidimensional definite integral

is to be calculated with known volume of

The most naive approach to compute is to sample points uniformly on : given uniform samples, can be approximated by

.

This is because the law of large numbers ensures that

.

One has to take into account that implementation issues such as pseudorandom number generators and limited floating point precision can lead to systematic errors, nevertheless, only in very particular cases this has to be taken into account.

Given the estimation of from, the error bars of can be estimated by the sample variance using the unbiased estimate of the variance:

which leads to

.

As long as the sequence is bounded, this variance decreases asymptotically to zero as . The estimation of the error of is thus

which decreases as and the familiar law of random walk applies: to reduce the error by a factor of 10 requires a 100-fold increase in the number of sample points. This result is quite strong in the sense that it does not depend on the number of dimensions of the integral: most of the deterministic methods like trapezoidal rule strongly depend on the dimension of the integral, because they use a grid to fill the space to compute the integral, and the grid grows exponentially with the dimensions.

The above expression provides a statistical estimate of the error on the result, which is not a strict error bound; random sampling of the region may not uncover all the important features of the function, resulting in an underestimate of the error.