13.2 The Monte Carlo Estimator
Suppose that we want to evaluate a 1D integral . Given a supply of uniform random variables , the Monte Carlo estimator says that the expected value of the estimator
, is in fact equal to the integral. This fact can be demonstrated with just a few steps. First, note that the PDF corresponding to the random variable must be equal to , since must both be a constant and also integrate to 1 over the domain . Algebraic manipulation then shows that
The restriction to uniform random variables can be relaxed with a small generalization. This is an extremely important step, since carefully choosing the PDF from which samples are drawn is an important technique for reducing variance in Monte Carlo (Section 13.10). If the random variables are drawn from some arbitrary PDF , then the estimator
can be used to estimate the integral instead. The only limitation on is that it must be nonzero for all where . It is similarly not too hard to see that the expected value of this estimator is the desired integral of :
Extending this estimator to multiple dimensions or complex integration domains is straightforward. samples are taken from a multidimensional (or “joint”) PDF, and the estimator is applied as usual. For example, consider the 3D integral
If samples are chosen uniformly from the box from to , the PDF is the constant value
and the estimator is
Note that the number of samples can be chosen arbitrarily, regardless of the dimension of the integrand. This is another important advantage of Monte Carlo over traditional deterministic quadrature techniques. The number of samples taken in Monte Carlo is completely independent of the dimensionality of the integral, while with standard numerical quadrature techniques the number of samples required is exponential in the dimension.
Showing that the Monte Carlo estimator converges to the right answer is not enough to justify its use; a good rate of convergence is important too. Although we will not derive its rate of convergence here, it has been shown that error in the Monte Carlo estimator decreases at a rate of in the number of samples taken. An accessible treatment of this topic can be found in Veach’s thesis (Veach 1997, p. 39). Although standard quadrature techniques converge faster than in one dimension, their performance becomes exponentially worse as the dimensionality of the integrand increases, while Monte Carlo’s convergence rate is independent of the dimension, making Monte Carlo the only practical numerical integration algorithm for high-dimensional integrals. We have already encountered some high-dimensional integrals in this book, and in Chapter 14 we will see that the path tracing formulation of the light transport equation is an infinite-dimensional integral!