Constructions of low-discrepancy sequences
|
|
There are some standard constructions of low-discrepancy sequences.
The Van der Corput sequence
Let
- <math>
n=\sum_{k=0}^{L-1}d_k(n)b^k <math>
be the b-ary representation of the positive integer n ≥ 1, i.e. 0 ≤ dk(n) < b − 1. Set
- <math>
g_b(n)=\sum_{k=0}^{L-1}d_k(n)b^{-k-1}. <math>
Then there is a constant C depending only on b such that (gb(n))n ≥ 1 satisfies
- <math>
D^*_N(g_b(1),...,g_b(N))\leq C\frac{\log N}{N}. <math>
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
- <math>
x(n)=(g_{b_1}(n),...,g_{b_s}(n)). <math>
Then there is a constant C depending only on b1, ..., bs, such that (x(n))n≥1 is a s-dimensional sequence with
- <math>
D^*_N(x(1),...,x(N))\leq C'\frac{(\log N)^s}{N}. <math>
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
- <math>
x(n)=(g_{b_1}(n),...,g_{b_{s-1}}(n),\frac{n}{N}) <math>
for n=1,...,N. Then
- <math>
D^*_N(x(1),...,x(N))\leq C\frac{(\log N)^{s-1}}{N} <math>
where C is a constant depending only on b1, ..., bs−1.