Sobol sequence

Sobol' sequences (also called LP τ sequences or (t, s) sequences in base 2) are a type of quasi-random low-discrepancy sequence. 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.

Sobol' sequences (also called LP τ sequences or (t, s) sequences in base 2) are a type of quasi-random low-discrepancy sequence. 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. \lim_{n\to\infty} \frac{1}{n} \sum_{i=1}^n f(x_i) = \int_{I^s} f 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 should fill minimizing the holes. Another good property would be that the projections of 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 \prod_{j=1}^s \left[ \frac{a_j}{b^{d_j}}, \frac{a_j+1}{b^{d_j}} \right], where a j and d j are non-negative integers, and a_j for all j in {1, ...,s}. Given 2 integers 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 \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 . Given a non-negative integer t, a (t,s)-sequence in base b is an infinite sequence of points x n such that for all integers k \geq 0, m \geq t , the sequence \{x_{kb^m}, ..., x_{(k+1)b^m-1}\} is a (t,m,s)-net in base b. In his article, Sobol’ described Π τ -meshes and LP τ sequences, which are (t,m,s)-nets and (t,s)-sequences in base 2 respectively. The terms (t,m,s)-nets and (t,s)-sequences in base b (also called Niederreiter sequences) were coined in 1988 by Harald Niederreiter. The term Sobol’ sequences was introduced in late English-speaking papers in comparison with Halton, Faure and other low-discrepancy sequences. As for the generation of Sobol’ numbers, they are clearly aided by the use of Gray code G(n)=n \oplus \lfloor n/2 \rfloor instead of n for constructing the n-th point draw. Suppose we have already generated all the Sobol’ sequence draws up to n − 1 and kept in memory the values x n−1,j for all the required dimensions. Since the Gray code G(n) differs from that of the preceding one G(n − 1) by just a single, say the k-th, bit (which is a rightmost zero bit of n − 1), all that needs to be done is a single XOR operation for each dimension in order to propagate all of the x n−1 to x n , i.e. x_{n,i} = x_{n-1,i} \oplus v_{k,i}. {{math theorem | math_statement = The d-dimensional Sobol’ sequence possesses Property A if and only if \det(\mathbf{V}_d) \equiv 1 \pmod{2}, where V d is the d × d binary matrix defined by \mathbf{V}_d := \begin{pmatrix} {v_{1,1,1}}&{v_{2,1,1}}&{\dots}&{v_{d,1,1}}\\ {v_{1,2,1}}&{v_{2,2,1}}&{\dots}&{v_{d,2,1}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {v_{1,d,1}}&{v_{2,d,1}}&{\dots}&{v_{d,d,1}} \end{pmatrix}, with v k,j,m denoting the m-th digit after the binary point of the direction number v k,j = (0.v k,j,1 v k,j,2 ...) 2 . }} {{math theorem | math_statement = The d-dimensional Sobol’ sequence possesses Property A' if and only if \det(\mathbf{U}_d) \equiv 1 \pmod{2}, where U d is the 2d × 2d binary matrix defined by \mathbf{U}_d := \begin{pmatrix} {v_{1,1,1}}&{v_{1,1,2}}&{v_{2,1,1}}&{v_{2,1,2}}&{\dots}&{v_{d,1,1}}&{v_{d,1,2}}\\ {v_{1,2,1}}&{v_{1,2,2}}&{v_{2,2,1}}&{v_{2,2,2}}&{\dots}&{v_{d,2,1}}&{v_{d,2,2}}\\ {\vdots}&{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}&{\vdots}\\ {v_{1,2d,1}}&{v_{1,2d,2}}&{v_{2,2d,1}}&{v_{2,2d,2}}&{\dots}&{v_{d,2d,1}}&{v_{d,2d,2}} \end{pmatrix}, with v k,j,m denoting the m-th digit after the binary point of the direction number v k,j = (0.v k,j,1 v k,j,2 ...) 2 . }} Tests for properties A and A’ are independent. Thus it is possible to construct the Sobol’ sequence that satisfies both properties A and A’ or only one of them. Arguably the easiest choice for the initialisation numbers is just to have the l-th leftmost bit set, and all other bits to be zero, i.e. m k,j = 1 for all k and j. This initialisation is usually called unit initialisation. However, such a sequence fails the test for Property A and A’ even for low dimensions and hence this initialisation is bad.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372574504 under CC BY-SA 4.0; modifications have been made.