quasi-Monte Carlo
/ KWAH-zee MON-tee KAR-loh /
Ordinary Monte Carlo throws points at random, and random points are clumpy — by chance some regions get crowded while others are left bare, and that wasteful clumping is what limits the accuracy. Quasi-Monte Carlo asks a sharp question: what if, instead of random points, we placed points that are deliberately spread out as EVENLY as possible, with no gaps and no clusters? Such carefully designed points fill space more uniformly than random ones and can integrate faster, while keeping the dimension-friendliness that makes Monte Carlo win in the first place.
The points come from a LOW-DISCREPANCY SEQUENCE — a deterministic, non-random list of points (Sobol, Halton, Faure) engineered so that every sub-box of the domain contains a fraction of the points close to its volume; the maximum mismatch is the 'discrepancy', and these sequences make it small. You still estimate the integral as the plain average of the integrand over the points — same formula as Monte Carlo — but because the points cover the space so evenly, the error falls much faster. The classic Koksma-Hlawka theory gives a worst-case error of order (log N)^d / N, which is close to 1/N — dramatically better than Monte Carlo's 1/sqrt(N). For example, going from N to 100N can buy nearly 100x accuracy with QMC, versus only 10x with plain Monte Carlo.
It sounds like a free lunch, and partly it is, but the honesty matters. The (log N)^d / N bound carries a (log N)^d factor that grows with dimension d, so the advantage over plain Monte Carlo weakens as d becomes large or for non-smooth integrands; for very high effective dimension QMC may revert toward 1/sqrt(N) behaviour. The deterministic points also give NO automatic error bar — you lose the easy s/sqrt(N) confidence interval — so practitioners use 'randomized QMC' (randomly shifted or scrambled sequences) to recover both an unbiased estimate and an honest error estimate from a few independent randomizations. Used on smooth, moderate-dimensional integrals (option pricing, certain physics), QMC is a genuine and widely used speed-up.
Integrate a smooth function over the 5-dimensional unit cube. Plain Monte Carlo with N = 10,000 random points gives an error around 1/sqrt(10000) = 0.01. A Sobol low-discrepancy sequence of the same 10,000 points, covering the cube far more evenly, can reach an error closer to (log N)^5 / N, often one to two digits smaller — same number of integrand evaluations, much better answer.
Evenly spread deterministic points integrate near 1/N instead of 1/sqrt(N).
QMC's near-1/N advantage erodes in very high dimension or for non-smooth integrands, where the (log N)^d factor bites. And deterministic points give NO built-in error bar — use randomized (scrambled) QMC to recover an honest confidence interval.