Sobol sequence

Sobol sequences (also called LP_τ sequences or (t, s) sequences in base 2) are an example of quasi-random low-discrepancy sequences. They were first introduced by the Russian mathematician Ilya M. Sobol (Илья Меерович Соболь) in 1967.

These sequences use a base of two to form successively finer uniform partitions of the unit interval and then reorder the coordinates in each dimension.

Let I^s = [0,1]^s be the s-dimensional unit hypercube, and f a real integrable function over I^s. The original motivation of Sobol was to construct a sequence x_n in I^s so that

and the convergence be as fast as possible.

It is more or less clear that for the sum to converge towards the integral, the points x_n should fill I^s minimizing the holes. Another good property would be that the projections of x_n on a lower-dimensional face of I^s leave very few holes as well. Hence the homogeneous filling of I^s does not qualify because in lower dimensions many points will be at the same place, therefore useless for the integral estimation.

These good distributions are called (t,m,s)-nets and (t,s)-sequences in base b. To introduce them, define first an elementary s-interval in base b a subset of I^s of the form

where a_j and d_j are non-negative integers, and ${\displaystyle a_{j}<b^{d_{j}}}$ for all j in {1, ...,s}.

Given 2 integers ${\displaystyle 0\leq t\leq m}$, a (t,m,s)-net in base b is a sequence x_n of b^m points of I^s such that ${\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}}$ for all elementary interval P in base b of hypervolume λ(P) = b^t−m.

...
Wikipedia