Monte Carlo integration converges at O(n^-1/2) regardless of problem dimension, unlike quadrature methods

Classical numerical integration (quadrature) requires exponentially more samples as the number of dimensions increases — a grid with k points per dimension needs k^d total samples for a d-dimensional problem. Monte Carlo estimation converges at O(n^-1/2) regardless of dimension: each additional sample halves the error squared, independent of how many dimensions are being integrated over. The rendering equation integrates over the hemisphere (2D), across all light sources, and through multiple path bounces — a very high-dimensional problem. This dimensional independence makes Monte Carlo the only practical integration algorithm for production rendering, despite its slow O(n^-1/2) convergence on low-dimensional problems where quadrature would excel.

Examples

A path tracer integrating 5-bounce indirect illumination from 100 area lights is effectively a very high-dimensional integral. Quadrature would need astronomically many samples; Monte Carlo with 256 samples/pixel can produce a reasonable estimate.

Assessment

Explain why adding a second indirect bounce to a path tracer doesn’t require quadratically more samples per pixel (hint: each bounce adds dimensions). State the convergence rate and what techniques can improve it beyond the basic O(n^-1/2) bound.