Quasi-Monte Carlo

Imagine trying to estimate the area of an irregular shape by throwing darts at a board blindfolded. That is essentially Monte Carlo integration: toss random points at a region and count what fraction land inside. Throw enough darts and the fraction converges to the true area.

The catch is randomness itself. Random points cluster in some places and leave gaps in others purely by chance. Those accidents slow convergence: the error of plain Monte Carlo shrinks at only $O(1/\sqrt{n})$, meaning you need four times as many points to halve the error.

Quasi-Monte Carlo (QMC) replaces those random darts with low-discrepancy sequences — point sets designed to fill every corner of the space as evenly as possible, with no gaps or clusters. The most famous are the Halton and Sobol sequences. The result is faster convergence, often approaching $O(1/n)$ or better in practice, with the same computational effort.

The key concept is discrepancy: a measure of how unevenly a set of points covers the unit cube. Low-discrepancy sequences minimize this unevenness systematically, turning a random guessing game into a carefully laid-out grid — one that adapts to the dimension of the problem.

Both panels below drop points into the unit square. The left panel uses uniform random sampling; the right uses a Sobol sequence — a low-discrepancy sequence that systematically avoids gaps.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label for="nSlider">{{label_n}} <strong id="nVal">64</strong></label>
  <input type="range" id="nSlider" min="4" max="512" value="64" step="4">
  <button id="newRandom" type="button">{{btn_new_random}}</button>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-title">{{title_random}}</div>
    <canvas id="canvasRandom" width="200" height="200"></canvas>
    <div class="disc-label">{{label_disc}} <span id="discRandom">—</span></div>
  </div>
  <div class="panel">
    <div class="panel-title">{{title_sobol}}</div>
    <canvas id="canvasSobol" width="200" height="200"></canvas>
    <div class="disc-label">{{label_disc}} <span id="discSobol">—</span></div>
  </div>
</div>
<p class="hint">{{hint_disc}}</p>

/* {{c_css_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .6rem; margin-bottom: .8rem; }
label { font-size: .9rem; }
input[type=range] { flex: 1 1 120px; min-width: 80px; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
button:hover { background: #2a4a78; }
.panels { display: flex; gap: 1rem; flex-wrap: wrap; justify-content: center; }
.panel { display: flex; flex-direction: column; align-items: center; gap: .35rem; }
.panel-title { font-weight: 700; font-size: .9rem; text-align: center; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; background: #f5f8fa;
         width: 200px; height: 200px; display: block; }
.disc-label { font-size: .82rem; color: #555; }
.disc-label span { font-weight: 700; color: #1d3557; }
.hint { font-size: .8rem; color: #666; margin: .6rem 0 0; line-height: 1.45; }

// Code not found

Notice how random points form visible clusters and leave empty patches, while the Sobol points spread themselves almost like a tightening grid. The discrepancy score shown below each panel measures the worst-case gap between the fraction of points in any axis-aligned rectangle and the rectangle's true area. Lower is better — and the Sobol panel wins consistently.

The theoretical backbone is the Koksma–Hlawka inequality (1961), which bounds integration error:

$$|I - \hat{I}_n| \leq V(f) \cdot D^*(P_n)$$

Here $V(f)$ is the variation of the integrand (how wiggly the function is), and $D^*(P_n)$ is the star discrepancy of the point set — a measure of how far from uniform the points are. The bound says: use points with lower discrepancy and you get a tighter error guarantee.

• Random points achieve discrepancy $D^* \approx O(1/\sqrt{n})$ with high probability, matching the $O(1/\sqrt{n})$ convergence rate of plain Monte Carlo.
• Low-discrepancy sequences achieve $D^* = O((\log n)^d / n)$ in $d$ dimensions. For small $d$ this is dramatically better; the $(\log n)^d$ factor grows with dimension, which is why QMC's advantage fades in very high-dimensional problems.

Why does the Sobol sequence work? It is built from binary arithmetic: each coordinate in dimension $k$ uses a different prime-base van der Corput sequence, and the coordinates are scrambled to minimize cross-dimensional correlations. The result is a sequence where every $2^m$ consecutive points form a $(t,m,s)$-net — a combinatorial object that guarantees balanced coverage in every axis-aligned sub-box.

Halton sequences use a simpler construction: represent $n$ in base $b_k$ (the $k$-th prime) and reverse the digits. Base 2 gives $0, 0.5, 0.25, 0.75, \dots$ — filling the gaps perfectly. In higher dimensions, the chosen bases must be coprime, which is why primes are used.

The curse of dimensionality is the real limit: as $d$ grows, the $(\log n)^d$ factor eventually overwhelms the $1/n$ gain, and plain Monte Carlo catches up. In practice QMC shines for $d \leq 10$ to $20$ dimensions — exactly the range common in finance, engineering and physics.

The speed advantage of QMC is not academic — it shows up wherever high-dimensional integrals must be computed in finite time:

• Financial derivatives pricing: computing the expected payoff of an option over thousands of market scenarios is a high-dimensional integral. Banks switched from Monte Carlo to QMC (especially Sobol) in the 1990s and cut computation time by factors of 10–100 for the same accuracy.
• Computer graphics (path tracing): rendering a photo-realistic image means integrating light over all possible paths. Modern path tracers (games, film VFX) use blue-noise and low-discrepancy point sets to reduce visible noise per sample — this is why ray-traced games converge to clean images faster.
• Uncertainty quantification (UQ): simulating how manufacturing tolerances, weather uncertainty or sensor noise propagate through a physical model is a multi-dimensional integral over the uncertain inputs. QMC reduces the number of costly simulations needed.
• Numerical cubature in physics: computing multi-dimensional integrals in particle physics, quantum chemistry and statistical mechanics benefits from the same discrepancy reduction.

Want to understand the randomness that QMC replaces? See how plain randomized algorithms work, or explore Monte Carlo tree search to see randomness used constructively in decision-making.

Quasi-Monte Carlo is a beautiful inversion: instead of relying on randomness to eventually cover space, it engineers coverage from the start. Low-discrepancy sequences like Sobol and Halton tile the integration domain without gaps, and the Koksma–Hlawka inequality guarantees the payoff — faster convergence, provably.

The lesson extends beyond integrals: structured, deliberate exploration of a space often beats blind random search. For moderate dimensions, QMC is a free upgrade to any Monte Carlo computation. When the dimension grows large enough that $(\log n)^d$ bites, plain Monte Carlo reasserts itself — and that transition point is itself a window into the geometry of high-dimensional space.

The next time you see a ray-traced scene converge cleanly, or an option price computed in milliseconds, there is a good chance a low-discrepancy sequence is quietly doing the work — too evenly spaced to be random, and faster because of it.