Neatly explained in https://medium.com/@antoine_savine/sobol-sequence-explained-188f422b246b

A Sobol sequence is a deterministic low-discrepancy (quasi-random) sequence , introduced by Sobol’ in 1967. It replaces the pseudo-random points of Monte Carlo integration with points that fill the unit cube far more evenly, which is the basis of quasi-Monte Carlo.

Why: discrepancy

The star discrepancy of points measures the worst mismatch between the fraction of points in an anchored box and the box’s volume:

The Koksma-Hlawka inequality bounds the integration error by , where is the Hardy-Krause variation of . Random points give (up to logarithmic factors), whereas Sobol points give . For smooth, effectively low-dimensional integrands, common in option pricing, this means an error close to instead of .

Construction

Each coordinate is built independently in base 2, with all arithmetic on binary fractions done by bitwise XOR, denoted .

  1. Pick a distinct primitive polynomial over for each dimension, with .
  2. Choose initial odd integers with , and extend them by the recurrence
  1. Define the direction numbers , binary fractions with bits.
  2. Write in binary. The -th point is

In matrix form, the bits of are over , with an upper triangular generator matrix whose columns are the bits of : a digital sequence. Implementations use the Antonov-Saleev Gray code ordering instead, with the position of the lowest zero bit of , which costs one XOR per point and coordinate and only permutes the points within each block of .

The quality depends on the free choices ; standard tables are those of Joe and Kuo (Constructing Sobol sequences with better two-dimensional projections, SIAM J. Sci. Comput. 30, 2008), used for example by scipy.stats.qmc.Sobol.

Example in two dimensions

  • Dimension 1 uses all , so and is the van der Corput sequence (the bits of mirrored about the binary point).
  • Dimension 2 uses () and , so : and in binary.

In Gray code order, the first four points are : exactly one point in each cell of the grid and in each strip of the and grids. Every dyadic box of volume holds exactly one point, the best possible balance ( below).

Properties and practice

  • Stratification: a Sobol sequence is a -sequence in base 2. Every block places exactly points in each dyadic box of volume . The quality parameter grows with .
  • Use sample sizes , since the balance properties hold for such blocks.
  • Being deterministic, a single run gives no error estimate. Randomised quasi-Monte Carlo fixes this: apply a random digital shift or Owen scrambling, repeat with independent randomisations, and use the spread of the estimates. Scrambling preserves the property and can improve the convergence rate for smooth integrands.
  • Order the variables by importance (for path simulation, a Brownian bridge construction puts most of the variance in the first coordinates), because the early dimensions are the most uniform and high-index two-dimensional projections can be poor.
  • Discrepancy bounds degrade as , so for large the advantage relies on the integrand having low effective dimension.