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 .
- Pick a distinct primitive polynomial over for each dimension, with .
- Choose initial odd integers with , and extend them by the recurrence
- Define the direction numbers , binary fractions with bits.
- 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.