QuasiMonteCarlo

Quasi-Monte Carlo (QMC) methods are numerical techniques for estimating integrals and expectations by evaluating a function at deterministically generated, low-discrepancy point sets rather than at randomly drawn samples. The goal is to achieve more uniform coverage of the target space and faster convergence for many problems.

QMC uses point sets such as Sobol', Halton, Niederreiter, and lattice-based sequences or digital nets. These sequences are designed to fill the unit cube [0,1)^d more uniformly than random samples. To compute integrals over [0,1)^d, one typically evaluates the function at N points and averages the results; for non-uniform targets, a suitable transformation maps samples from the unit cube to the desired distribution. Randomized variants, such as scrambling Sobol' sequences, preserve low discrepancy while enabling empirical error estimation.

Convergence theory for QMC is based on the Koksma-Hlawka inequality, which bounds the integration error by the product of the function’s variation (in the sense of Hardy and Krause) and the discrepancy of the point set. For common low-discrepancy sequences, the discrepancy scales like O((log N)^d / N), leading to a convergence rate near O((log N)^d / N) rather than the O(N^{-1/2}) rate of standard Monte Carlo. While advantageous for smooth or low-variation integrands, performance can deteriorate with high dimension or highly irregular functions.

Applications of QMC span finance (option pricing and risk assessment), physical and engineering simulations, computer graphics and rendering, and uncertainty quantification. Variants such as randomized QMC and scrambling techniques provide practical error estimates and robustness, while dimension-reduction strategies and appropriate transforms help extend effectiveness to higher-dimensional problems.