Van der Corput sequence

A van der Corput sequence is a low-discrepancy sequence over the unit interval first published in 1935 by the Dutch mathematician J. G. van der Corput. It is constructed by reversing the base "n" representation of the sequence of natural numbers (1, 2, 3, …). For example, the decimal van der Corput sequence begins:

:0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32, …

whereas the binary van der Corput sequence can be written as:

:0.1₂, 0.01₂, 0.11₂, 0.001₂, 0.101₂, 0.011₂, 0.111₂, 0.0001₂, 0.1001₂, 0.0101₂, 0.1101₂, 0.0011₂, 0.1011₂, 0.0111₂, 0.1111₂, …

or, equivalently, as:

:$frac\{1\}\{2\},\; frac\{1\}\{4\},\; frac\{3\}\{4\},\; frac\{1\}\{8\},\; frac\{5\}\{8\},\; frac\{3\}\{8\},\; frac\{7\}\{8\},\; frac\{1\}\{16\},\; frac\{9\}\{16\},\; frac\{5\}\{16\},\; frac\{13\}\{16\},\; frac\{3\}\{16\},\; frac\{11\}\{16\},\; frac\{7\}\{16\},\; frac\{15\}\{16\},\; ldots$

The elements of the van der Corput sequence (in any base) form a dense set in the unit interval: for any real number in [0, 1] there exists a subsequence of the van der Corput sequence that converges towards that number. They are also uniformly distributed over the unit interval.

ee also

* Constructions of low-discrepancy sequences

References

* J. G. van der Corput, "Verteilungsfunktionen". Proc. Ned. Akad. v. Wet., 38:813–821, 1935
*

External links

* [http://mathworld.wolfram.com/vanderCorputSequence.html van der Corput sequence] at MathWorld