Computing Integrals

The variance of the Crude Monte Carlo estimate is O(1/m). This means that improving the estimate by one decimal digit requires a hundred-fold effort. Amazingly enough, the computational complexity is independent of the dimension n, which makes Monte Carlo attractive for higher dimensional problems.

It is also possible to use variance reducing techniques that can give substantial efficiency gain. We covered:

Stratified sampling: The integration region A is broken into several pieces, in each of which ideally the variation of the function f is the same.

Importance sampling: The objective is to concentrate the sample of points to parts of the regions which contribute most to the integral.

Control variates: A function g approximating f that can be integrated analytically is used. Monte Carlo is then used to integrate the difference between f and g which ideally is constant in A.

Antithetic variates: Opposite to the choice in "control variates" a second estimator having the same expectation as the original estimator but a strong negative correlation with it is used, with the objective that the variation of half the sum of these would be less than the variation of the original.