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

n=\sum_{k=0}^{L-1}d_k(n)b^k

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

g_b(n)=\sum_{k=0}^{L-1}d_k(n)b^{-k-1}.

Then there is a constant C depending only on b such that (gb(n))n ≥ 1 satisfies

D^*_N(g_b(1),\dots,g_b(N))\leq C\frac{\log N}{N}.

[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 b1, ..., bs be arbitrary coprime integers greater than 1. Define

x(n)=(g_{b_1}(n),\dots,g_{b_s}(n)).

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

D^*_N(x(1),\dots,x(N))\leq C'\frac{(\log N)^s}{N}.

[edit] The Hammersley set

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

x(n)=(g_{b_1}(n),\dots,g_{b_{s-1}}(n),\frac{n}{N})

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

D^*_N(x(1),\dots,x(N))\leq C\frac{(\log N)^{s-1}}{N}

where C is a constant depending only on b1, ..., bs−1.