Sobol Sequence

The Sobolʹ sequences [1] are a digital (ts, s)-sequences over ℤ2, where

ts = $\displaystyle \sum_{{i=1}}^{{s}}$(deg pi − 1),

with p1 = x ∈ ℤ2[x] and pi+1 denoting the ith primitive polynomial over ℤ2 ordered by degree.

Sobolʹ sequences were the first known constructions yielding (t, s)-sequences for arbitrary dimensions s. They were introduced long before the theory of (t, s)-sequences over arbitrary finite fields Fb was established in [2]. However, they only exist for b = 2, and even in this case, the resulting t parameter is not optimal for s > 3. For s > 7, even the Niederreiter sequence, which is equally easy to implement, yields lower t-values.

For s = 1 the Sobolʹ sequence (defined by the polynomial p1 = x) is a (0, 1)-sequence identical to the van der Corput sequence in base 2.

See Also

References

[1]Ilʹya M. Sobolʹ.
On the distribution of points in a cube and the approximate evaluation of integrals.
U.S.S.R. Computational Mathematics and Mathematical Physics, 7(4):86–112, 1967.
[2]Harald Niederreiter.
Point sets and sequences with small discrepancy.
Monatshefte für Mathematik, 104(4):273–337, December 1987.
doi:10.1007/BF01294651 MR918037 (89c:11120)
[3]Gary L. Mullen, Arijit Mahalanabis, and Harald Niederreiter.
Tables of (t, m, s)-net and (t, s)-sequence parameters.
In Harald Niederreiter and Peter Jau-Shyong Shiue, editors, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, volume 106 of Lecture Notes in Statistics, pages 58–86. Springer-Verlag, 1995.

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Sobol Sequence.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_SSobol.html

Show usage of this method