Van der Corput sequence

From Wikipedia, the free encyclopedia

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:

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.

[edit] See also

• Constructions of low-discrepancy sequences

[edit] References

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

[edit] External links

• van der Corput sequence at MathWorld