Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 38 ยท Monte Carlo Integration

Quasi-Monte Carlo and Low-Discrepancy Sequences

Replace random points with evenly spread low-discrepancy sequences (van der Corput, Halton, Sobol) and get faster convergence for smooth integrals.

Random points have a drawback: by chance they clump and leave gaps. In a plot of 100 random points you can usually spot empty patches and crowded spots. Quasi-Monte Carlo (QMC) replaces random points with deterministic points designed to fill space evenly. For smooth integrals this can converge close to 1/N instead of 1/โˆšN. This lesson builds such points from scratch and compares them with ordinary random sampling.

Discrepancy: measuring evenness

The discrepancy of a set of points measures how far the points are from perfectly even coverage: take any box inside the unit cube, compare the fraction of points inside it with the box's volume, and look at the worst case. Random points have discrepancy around 1/โˆšN. Low-discrepancy sequences achieve about (log N)^d / N, much better for moderate d.

The Koksmaโ€“Hlawka inequality links this to integration: the integration error is at most (a measure of how wiggly f is) ร— (the discrepancy of the points). So evenly spread points guarantee small error for functions that are not too rough.

The van der Corput sequence

The simplest low-discrepancy sequence works in one dimension. To get the n-th point in base b (take b = 2): write n in binary, then mirror its digits around the decimal point.

n binary mirrored value
1 1 0.1 0.5
2 10 0.01 0.25
3 11 0.11 0.75
4 100 0.001 0.125
5 101 0.101 0.625

Each new point lands in the largest remaining gap, so the points are always spread out, however many you take.

Python van der Corput sequence from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The random points leave gaps and form clumps; the van der Corput points form an even spread.

Halton sequences in many dimensions

For d dimensions, the Halton sequence uses a different prime base for each coordinate: base 2 for xโ‚, base 3 for xโ‚‚, base 5 for xโ‚ƒ, and so on. Its point number i is (ฯ†โ‚‚(i), ฯ†โ‚ƒ(i), ฯ†โ‚…(i), โ€ฆ), where ฯ†_b is the van der Corput function in base b. Different bases keep the coordinates from falling into step with each other.

Python 2D Halton points versus random points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Integration with QMC

Now compare the two. We integrate a smooth function on the unit square, f(x, y) = e^(x+y). The exact answer is (e โˆ’ 1)ยฒ โ‰ˆ 2.9525. For QMC we use the Halton points above; for ordinary Monte Carlo we use random points, repeated several times to measure the typical error.

Python Quasi-Monte Carlo versus Monte Carlo

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For this smooth integrand the Halton error falls far faster than the random one. The gap tends to widen as N grows.

Sobol sequences and scipy.stats.qmc

Halton sequences degrade as the dimension grows (the high prime bases produce correlated-looking patterns for small N). Sobol sequences, built from binary arithmetic, are the usual choice for dimensions above about 10, and they have a special property: their best accuracy occurs when N is a power of 2. SciPy provides them in scipy.stats.qmc, along with scrambling.

Python Scrambled Sobol points with SciPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The integrand's exact integral is 1 because each factor integrates to 1 + 0.5ยท(0.5 โˆ’ 0.5) = 1. If the code reports a Sobol warning about the number of points, check that n is a power of 2, as here.

Randomized QMC: getting error bars back

Plain QMC is deterministic, so it has no statistical error bar. Randomized QMC adds random scrambling to a low-discrepancy set, keeping its evenness but making each run an unbiased estimate. Repeat with several independent scramblings and compute the standard error between them, exactly as in Chapter 1.

Python Error bar from independent scramblings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When QMC helps and when it does not

  • Helps for smooth integrands in low to moderate dimension, or when only a few dimensions matter.
  • Helps less for discontinuous integrands (such as hit-or-miss indicators) and for very rough functions; the advantage fades toward ordinary Monte Carlo.
  • Not suitable where independence of samples is essential (for example, simulating a queue where each customer must be an independent draw), unless used carefully.
  • Never mix a QMC point set with a random-looking sequence built by splicing; use the library tools and keep N a power of 2 for Sobol.

If your integrand is smooth, try scipy.stats.qmc.Sobol with scrambling before reaching for heavier tools. It is often a free accuracy gain.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a low-discrepancy sequence aim for?

    Low-discrepancy points are designed to avoid gaps and clumps, giving even coverage of the unit cube.
  2. 2. In the base-2 van der Corput sequence, what is the 3rd point (n = 3, binary 11)?

    Mirroring binary 11 across the point gives 0.11 in binary, which is 0.5 + 0.25 = 0.75.
  3. 3. Why does a Halton sequence use a different prime base for each coordinate?

    Pairwise coprime bases prevent the coordinates from correlating, so the points fill the cube.
  4. 4. Plain QMC has no statistical error bar. How can you obtain one?

    Each scrambled run is an unbiased estimate; the spread across runs gives a standard error.

Summary

  • Random points clump and leave gaps; low-discrepancy sequences (van der Corput, Halton, Sobol) fill space evenly.
  • For smooth integrands QMC can approach 1/N convergence, versus 1/โˆšN for plain Monte Carlo.
  • Halton uses one prime base per dimension; Sobol is preferred in higher dimensions with N a power of 2.
  • Scrambling (randomized QMC) restores unbiasedness and allows error bars.
  • The advantage shrinks for rough or discontinuous integrands.

Next: Antithetic Variates