Quasi-Monte Carlo Methods
Quasi-Monte Carlo replaces random samples with low-discrepancy sequences that fill space more evenly, converging faster than plain Monte Carlo.
Beating random with structure
Random Monte Carlo samples cluster and leave gaps by chance, which slows convergence. Quasi-Monte Carlo (QMC) replaces random draws with deterministic low-discrepancy sequences engineered to cover the unit hypercube as uniformly as possible. For smooth integrands this even coverage yields substantially faster convergence.
Discrepancy
Discrepancy measures how far a point set departs from perfect uniformity - the largest gap between the fraction of points in any sub-box and that box's volume. Low-discrepancy sequences minimize this. The Koksma-Hlawka inequality bounds integration error by the product of the integrand's variation and the point set's discrepancy, motivating the whole approach.
Common sequences
- Sobol sequences - widely used, with good high-dimensional projections
- Halton sequences - simple, built from radical inverses in different prime bases
- Faure sequences - based on prime-base permutations
- Lattice rules - shifted regular lattices tuned for periodic integrands
Convergence advantage
For sufficiently smooth functions, QMC error decreases roughly as (log N)^d over N - close to order one over N, versus one over the square root of N for random Monte Carlo. In practice this can mean an order of magnitude fewer samples for the same accuracy, though the benefit erodes as dimension d grows and for non-smooth integrands.
Randomized QMC
Plain QMC gives no built-in error estimate because it is deterministic. Randomized QMC - scrambling or random shifting of the sequence - restores an unbiased estimator and lets you estimate error from a few independent randomizations, combining QMC accuracy with Monte Carlo error bars.
Use and cautions
QMC shines for smooth, moderate-dimensional integrals such as propagating a handful of uncertain parameters through a Kronos surrogate. For high effective dimension or discontinuous responses its advantage fades and randomized or plain Monte Carlo may be safer. Choosing the sequence and checking effective dimension are part of using it well.