## 13.2 The Monte Carlo Estimator

We can now define the basic Monte Carlo estimator, which approximates the value of an arbitrary integral. It is the foundation of the light transport algorithms defined in Chapters 14, 15, and 16.

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!