Monte Carlo & Randomized Methods

a low-discrepancy sequence

If you want to place a hundred dots in a square so they cover it as fairly as possible, true random dots are surprisingly bad — they leave holes and clumps. A regular grid is even but only works for special counts and lines points up in suspicious rows. A low-discrepancy sequence is the clever middle path: a list of points that looks irregular like random but is engineered to spread out evenly at every scale, with no large empty gaps and no dense clusters, and that you can extend point by point without redoing the layout.

The technical measure of 'evenly spread' is DISCREPANCY: for any sub-box of the unit cube, compare the fraction of points that fall inside it with the box's volume; the discrepancy is the worst mismatch over all boxes. Random points have discrepancy of order 1/sqrt(N); a low-discrepancy sequence drives it down to about (log N)^d / N, far smaller. The famous constructions are clever number-theoretic recipes: the Halton sequence builds each coordinate by reversing the digits of the counter n in a different prime base (the 1D van der Corput sequence is base 2: 1/2, 1/4, 3/4, 1/8, 5/8, ...), filling gaps systematically; Sobol sequences use binary 'direction numbers' and are the practical workhorse in finance and graphics. They are deterministic — the same sequence every time, no seed.

These sequences are the engine inside quasi-Monte Carlo, and that is where their value shows. The honest caveats are about scaling and structure. The Halton sequence degrades in high dimensions because high-prime-base coordinates become strongly correlated for the first several points (so people scramble or skip them); Sobol needs carefully chosen direction numbers and good initial points. The (log N)^d factor means the uniformity edge thins as dimension grows. And because the points are deterministic, you get no statistical error bar by default — randomized scrambling restores one. For smooth integrands in low-to-moderate dimension, though, low-discrepancy points beat random ones cleanly.

The 1D van der Corput sequence (base 2) is 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, ...: each new point bisects the largest remaining gap, so the line is always as evenly covered as possible. The 2D Halton sequence pairs this base-2 coordinate with a base-3 one, scattering points across the square far more uniformly than random pairs.

Deterministic points that fill space evenly at every scale — low discrepancy, no clumps.

Not all low-discrepancy sequences scale gracefully: Halton's high-dimension coordinates correlate badly on the first points (scramble or skip them), and the (log N)^d factor erodes uniformity as dimension grows. Deterministic points carry no error bar unless you randomize them.

Also called
quasi-random sequenceSobol sequenceHalton sequence低差異數列準隨機序列