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 integral Subscript a Superscript b Baseline f left-parenthesis x right-parenthesis normal d x . Given a supply of uniform random variables upper X Subscript i Baseline element-of left-bracket a comma b right-bracket , the Monte Carlo estimator says that the expected value of the estimator

upper F Subscript upper N Baseline equals StartFraction b minus a Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts f left-parenthesis upper X Subscript i Baseline right-parenthesis comma

upper E left-bracket upper F Subscript upper N Baseline right-bracket , is in fact equal to the integral. This fact can be demonstrated with just a few steps. First, note that the PDF p left-parenthesis x right-parenthesis corresponding to the random variable upper X Subscript i must be equal to 1 slash left-parenthesis b minus a right-parenthesis , since p must both be a constant and also integrate to 1 over the domain left-bracket a comma b right-bracket . Algebraic manipulation then shows that

StartLayout 1st Row 1st Column upper E left-bracket upper F Subscript upper N Baseline right-bracket 2nd Column equals upper E left-bracket StartFraction b minus a Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts f left-parenthesis upper X Subscript i Baseline right-parenthesis right-bracket 2nd Row 1st Column Blank 2nd Column equals StartFraction b minus a Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts upper E left-bracket f left-parenthesis upper X Subscript i Baseline right-parenthesis right-bracket 3rd Row 1st Column Blank 2nd Column equals StartFraction b minus a Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts integral Subscript a Superscript b Baseline f left-parenthesis x right-parenthesis p left-parenthesis x right-parenthesis normal d x 4th Row 1st Column Blank 2nd Column equals StartFraction 1 Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts integral Subscript a Superscript b Baseline f left-parenthesis x right-parenthesis normal d x 5th Row 1st Column Blank 2nd Column equals integral Subscript a Superscript b Baseline f left-parenthesis x right-parenthesis normal d x period EndLayout

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 upper X Subscript i are drawn from some arbitrary PDF p left-parenthesis x right-parenthesis , then the estimator

upper F Subscript upper N Baseline equals StartFraction 1 Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts StartFraction f left-parenthesis upper X Subscript i Baseline right-parenthesis Over p left-parenthesis upper X Subscript i Baseline right-parenthesis EndFraction
(13.3)

can be used to estimate the integral instead. The only limitation on p left-parenthesis x right-parenthesis is that it must be nonzero for all  x where StartAbsoluteValue f left-parenthesis x right-parenthesis EndAbsoluteValue greater-than 0 . It is similarly not too hard to see that the expected value of this estimator is the desired integral of  f :

StartLayout 1st Row 1st Column upper E left-bracket upper F Subscript upper N Baseline right-bracket 2nd Column equals upper E left-bracket StartFraction 1 Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts StartFraction f left-parenthesis upper X Subscript i Baseline right-parenthesis Over p left-parenthesis upper X Subscript i Baseline right-parenthesis EndFraction right-bracket 2nd Row 1st Column Blank 2nd Column equals StartFraction 1 Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts integral Subscript a Superscript b Baseline StartFraction f left-parenthesis x right-parenthesis Over p left-parenthesis x right-parenthesis EndFraction p left-parenthesis x right-parenthesis normal d x 3rd Row 1st Column Blank 2nd Column equals StartFraction 1 Over upper N EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts integral Subscript a Superscript b Baseline f left-parenthesis x right-parenthesis normal d x 4th Row 1st Column Blank 2nd Column equals integral Subscript a Superscript b Baseline f left-parenthesis x right-parenthesis normal d x period EndLayout

Extending this estimator to multiple dimensions or complex integration domains is straightforward. upper N samples upper X Subscript i are taken from a multidimensional (or “joint”) PDF, and the estimator is applied as usual. For example, consider the 3D integral

integral Subscript z 0 Superscript z 1 Baseline integral Subscript y 0 Superscript y 1 Baseline integral Subscript x 0 Superscript x 1 Baseline f left-parenthesis x comma y comma z right-parenthesis normal d x normal d y normal d z period

If samples upper X Subscript i Baseline equals left-parenthesis x Subscript i Baseline comma y Subscript i Baseline comma z Subscript i Baseline right-parenthesis are chosen uniformly from the box from left-bracket x 0 comma x 1 right-bracket times left-bracket y 0 comma y 1 right-bracket times left-bracket z 0 comma z 1 right-bracket , the PDF p left-parenthesis upper X right-parenthesis is the constant value

StartFraction 1 Over left-parenthesis x 1 minus x 0 right-parenthesis EndFraction StartFraction 1 Over left-parenthesis y 1 minus y 0 right-parenthesis EndFraction StartFraction 1 Over left-parenthesis z 1 minus z 0 right-parenthesis EndFraction comma

and the estimator is

StartFraction left-parenthesis x 1 minus x 0 right-parenthesis left-parenthesis y 1 minus y 0 right-parenthesis left-parenthesis z 1 minus z 0 right-parenthesis Over upper N EndFraction sigma-summation Underscript i Endscripts f left-parenthesis upper X Subscript i Baseline right-parenthesis period

Note that the number of samples upper N 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 upper O left-parenthesis StartRoot upper N EndRoot right-parenthesis 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 upper O left-parenthesis StartRoot upper N EndRoot right-parenthesis 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!