Constructions of low-discrepancy sequences

From Wikipedia, the free encyclopedia

There are some standard constructions of low-discrepancy sequences.

[edit] The van der Corput sequence

See main article van der Corput sequence

Let

be the b-ary representation of the positive integer n ≥ 1, i.e. 0 ≤ d_k(n) < b. Set

Then there is a constant C depending only on b such that (g_b(n))_{n ≥ 1} satisfies

[edit] The Halton sequence

See main article Halton sequences

The Halton sequence is a natural generalization of the van der Corput sequence to higher dimensions. Let s be an arbitrary dimension and b₁, ..., b_s be arbitrary coprime integers greater than 1. Define

Then there is a constant C depending only on b₁, ..., b_s, such that (x(n))_n≥1 is a s-dimensional sequence with

[edit] The Hammersley set

Let b₁,...,b_s-1 be coprime positive integers greater that 1. For given s and N, the s-dimensional Hammersley set of size N is defined by

for n = 1, ..., N. Then

where C is a constant depending only on b₁, ..., b_s−1.