Quasi-Monte Carlo And Sobol Sequences

Throw darts at a dartboard for an hour and you will find clusters where three darts landed almost on top of each other, and gaps where none landed at all. Every clustered dart is wasted information — it tells you nothing you didn't already know from its neighbour. Ordinary Monte Carlo simulation has exactly this problem: random points clump by chance, and the clumping is why the error shrinks so slowly, at a rate of $1/\sqrt{N}$ for $N$ paths. Quadruple the paths, and you only halve the error.

Fill the gaps on purpose

A Sobol sequence is a way of choosing points that never wastes a throw. The first point goes roughly in the middle of the empty space, the second fills the largest remaining gap, and so on, forever — every new point is placed where the existing points have left the biggest hole. There is no randomness in this at all; the sequence is a fixed, precomputed list. The technical name for "spread evenly, no clumps, no gaps" is low discrepancy, and it is the entire idea: a low-discrepancy sequence is what a dartboard would look like if every throw were aimed at the emptiest spot.

Because a Sobol sequence covers space more efficiently, a sum over its points converges to an integral faster than a sum over random points does. The bound behind this, due to Koksma and Hlawka, says the error of a quasi-Monte Carlo (QMC) estimate is roughly

$$\text{error}_{\text{QMC}} \;\approx\; C\,\frac{(\log N)^{d}}{N},$$

where $N$ is the number of points, $d$ is the dimension of the problem (roughly, the number of independent random draws each path needs), and $C$ is a constant depending on how wiggly the payoff is. In plain English: for a fixed low dimension, QMC error shrinks close to $1/N$, not $1/\sqrt{N}$ — for $N=10{,}000$, that is the difference between an error of about $0.01$ and one of about $0.0033$, roughly three times tighter for the same computing bill.

Worked example 1: estimating an integral with 4 points

Estimate $\int_0^1 x^2\,dx$, whose true value is $1/3 = 0.3333$.

Random points $x = 0.10, 0.85, 0.30, 0.62$: squares are $0.0100, 0.7225, 0.0900, 0.3844$. Mean $= 0.3017$. Error $= 0.0316$.

Evenly-spaced, low-discrepancy points $x = 0.125, 0.375, 0.625, 0.875$ (what a 1-D Sobol-type sequence gives with 4 points): squares are $0.0156, 0.1406, 0.3906, 0.7656$. Mean $= 0.3281$. Error $= 0.0052$.

Same number of function evaluations, six times less error, because the evenly-spaced points never left a gap the random points happened to miss.

Worked example 2: convergence for a digital option

Price a digital call that pays $1 if a stock ends above its strike, true probability $0.40$. Simulating this is just estimating a probability, so the error scales the same way as any Monte Carlo average.

Paths $N$	Random MC error ($\approx 0.5/\sqrt{N}$)	Sobol QMC error ($\approx (\log N)/N$, $d=1$)
$100$	$0.050$	$0.046$
$10{,}000$	$0.0050$	$0.00092$
$1{,}000{,}000$	$0.00050$	$0.0000138$

At small $N$ the two are close, but random error only ever divides by $\sqrt{10}=3.16$ each time you add a decade of paths, while the Sobol error divides by nearly $70$ once $N$ is large. That gap is the entire commercial case for QMC on a pricing desk: the same accuracy for a fraction of the runtime, which matters when a Monte Carlo book has to reprice thousands of times a day for risk.

These sampled stock paths are exactly what feeds a Monte Carlo option price — each path's terminal value is one sample point, the same way each dart in the earlier picture was one point in the unit square. Drag the volatility slider and watch how much a handful of ordinary random paths scatter; that scatter is the raw material a low-discrepancy sequence spreads out on purpose instead of leaving to chance.

What this means in practice

QMC is standard on desks that reprice large baskets of vanilla and path-dependent options intraday, because halving runtime for the same accuracy is real money in compute costs and lets risk be refreshed more often. It pairs naturally with a Brownian bridge construction, which pushes the "important" random draws into the first few dimensions where low discrepancy works best.