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.
Good distributions in the s-dimensional unit hypercube Let Is = [0,1]s be the s-dimensional unit hypercube, and f a real integrable function over Is. The original motivation of Sobol’ was to construct a sequence xn in Is so that
lim n → ∞ 1 n ∑ i = 1 n f ( x i ) = ∫ I s f {\displaystyle \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 xn should fill Is minimizing the holes. Another good property would be that the projections of xn on a lower-dimensional face of Is leave very few holes as well. Hence the homogeneous filling of Is 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 Is of the form
∏ j = 1 s [ a j b d j , a j + 1 b d j ] , {\displaystyle \prod _{j=1}^{s}\left[{\frac {a_{j}}{b^{d_{j}}}},{\frac {a_{j}+1}{b^{d_{j}}}}\right],}
where aj and dj are non-negative integers, and a j < b d j {\displaystyle a_{j}<b^{d_{j}}} for all j in {1, ...,s}. Given 2 integers 0 ≤ t ≤ m {\displaystyle 0\leq t\leq m} , a (t,m,s)-net in base b is a sequence xn of bm points of Is such that Card P ∩ { x 1 , . . . , x b m } = b t {\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}} for all elementary interval P in base b of hypervolume λ(P) = bt−m. Given a non-negative integer t, a (t,s)-sequence in base b is an infinite sequence of points xn such that for all integers k ≥ 0 , m ≥ t {\displaystyle k\geq 0,m\geq t} , the sequence { x k b m , . . . , x ( k + 1 ) b m − 1 } {\displaystyle \{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.
A fast algorithm A more efficient Gray code implementation was proposed by Antonov and Saleev. As for the generation of Sobol’ numbers, they are clearly aided by the use of Gray code G ( n ) = n ⊕ ⌊ n / 2 ⌋ {\displaystyle 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 xn−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 xn−1 to xn, i.e.
… excerpt ends here. Continue reading the full article.
