Low-Discrepancy Sequences and Quasi-Monte Carlo

Pricing an exotic option by Monte Carlo means averaging the payoff over many simulated paths, and the error in that average shrinks proportionally to $1/\sqrt{n}$ for $n$ paths — to cut the error in half you need four times as many paths, and standard random sampling is genuinely wasteful because pure chance leaves clumps and gaps in the space of scenarios it explores. Low-discrepancy sequences fix the "clumps and gaps" problem directly: they're deterministic point sets engineered to spread out as evenly as mathematically possible, and using them in place of random draws is called quasi-Monte Carlo.

An analogy: seating a theater randomly vs. deliberately

If you seat theater patrons by literally rolling dice for each seat, you'll get some rows packed and others nearly empty just by chance, even though the average density is right. If instead you seat people by a fixed, deliberate pattern designed to spread them evenly — front-to-back, side-to-side, no two people too close together — the theater fills up far more uniformly with the same number of patrons. Estimating a quantity by averaging over "seats" (sample points) works better when the seats are spread deliberately rather than left to chance, because uniform coverage of the space is what actually determines how good the average is, not the randomness itself.

The idea, one symbol at a time

Discrepancy is a formal measure of how unevenly a set of $n$ points fills a region — roughly, the largest gap between the fraction of points landing in any sub-region and that sub-region's true proportional size. A low-discrepancy sequence (Sobol, Halton, and van der Corput sequences are the standard examples) is a deterministic sequence engineered to keep this discrepancy as small as possible as $n$ grows. The payoff is in the error rate: plain Monte Carlo integration error scales as $O(1/\sqrt{n})$, while quasi-Monte Carlo error scales, for well-behaved integrands, closer to $O(1/n)$ — using the same $n$ points, the deterministic sequence's error can shrink an order of magnitude faster because it never wastes points on the accidental clumping that random sampling always produces to some degree.

Worked example 1: building the van der Corput sequence by hand

The van der Corput sequence in base 2 builds each point by taking the index $n$'s binary digits and mirroring them across the decimal point. For $n=1$: binary $1$ → mirrored $0.1_2 = 0.5$. For $n=2$: binary $10$ → mirrored $0.01_2 = 0.25$. For $n=3$: binary $11$ → mirrored $0.11_2 = 0.75$. For $n=4$: binary $100$ → mirrored $0.001_2 = 0.125$. The first four points are $0.5, 0.25, 0.75, 0.125$ — notice how they immediately split the unit interval into halves, then quarters, systematically filling gaps rather than clustering, which is exactly what four independent uniform random draws are not guaranteed to do.

Worked example 2: comparing convergence on a simple integral

Estimate $\int_0^1 x^2\,dx = 1/3$ using $n=100$ points. With standard Monte Carlo, repeated runs of 100 random uniform draws typically give an estimate accurate to around $\pm 0.03$ (consistent with an $O(1/\sqrt{100}) = 0.1$-scale error before the constant). With a low-discrepancy sequence of 100 points, the estimate is typically accurate to around $\pm 0.003$ — roughly a tenfold improvement for the same computational budget, consistent with the faster $O(1/n)$-type rate. For pricing a path-dependent option where each Monte Carlo path is expensive to simulate, this directly translates into needing far fewer simulated paths for the same pricing precision.

Watch how the running estimate settles as more points are added — the shaded $1/\sqrt{n}$ envelope shown is the standard Monte Carlo rate; a well-built low-discrepancy sequence would visibly hug the true value tighter than that envelope predicts, especially at larger $n$.

What this means in practice

Quasi-Monte Carlo is standard in pricing desks for computing Greeks and valuing basket or path-dependent derivatives in low-to-moderate dimensions, where its faster convergence directly cuts computation time. It's not a free upgrade everywhere: the theoretical advantage weakens as the number of dimensions grows very large (the "curse of dimensionality" partially reasserts itself), and because the points are deterministic rather than random, standard confidence-interval formulas built for random sampling don't directly apply — practitioners typically use randomized versions (scrambled sequences) to recover valid error estimates alongside the faster convergence.