Low-discrepancy sequence

In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x₁, ..., x_N has a low discrepancy.

Roughly speaking, the discrepancy of a sequence is low if the proportion of points in the sequence falling into an arbitrary set B is close to proportional to the measure of B, as would happen on average (but not for particular samples) in the case of an equidistributed sequence. Specific definitions of discrepancy differ regarding the choice of B (hyperspheres, hypercubes, etc.) and how the discrepancy for every B is computed (usually normalized) and combined (usually by taking the worst value).

Low-discrepancy sequences are also called quasi-random or sub-random sequences, due to their common use as a replacement of uniformly distributed random numbers. The "quasi" modifier is used to denote more clearly that the values of a low-discrepancy sequence are neither random nor pseudorandom, but such sequences share some properties of random variables and in certain applications such as the quasi-Monte Carlo method their lower discrepancy is an important advantage.

At least three methods of numerical integration can be phrased as follows. Given a set {x₁, ..., x_N} in the interval [0,1], approximate the integral of a function f as the average of the function evaluated at those points:

$\int_0^1 f(u)\,du \approx \frac{1}{N}\,\sum_{i=1}^N f(x_i).$

If the points are chosen as x_i = i/N, this is the rectangle rule. If the points are chosen to be randomly (or pseudorandomly) distributed, this is the Monte Carlo method. If the points are chosen as elements of a low-discrepancy sequence, this is the quasi-Monte Carlo method. A remarkable result, the Koksma–Hlawka inequality (stated below), shows that the error of such a method can be bounded by the product of two terms, one of which depends only on f, and the other one is the discrepancy of the set {x₁, ..., x_N}.

It is convenient to construct the set {x₁, ..., x_N} in such a way that if a set with N+1 elements is constructed, the previous N elements need not be recomputed. The rectangle rule uses points set which have low discrepancy, but in general the elements must be recomputed if N is increased. Elements need not be recomputed in the Monte Carlo method if N is increased, but the point sets do not have minimal discrepancy. By using low-discrepancy sequences, the quasi-Monte Carlo method has the desirable features of the other two methods.

Definition of discrepancy

The discrepancy of a set P = {x₁, ..., x_N} is defined, using Niederreiter's notation, as

$D_N(P) = \sup_{B\in J} \left| \frac{A(B;P)}{N} - \lambda_s(B) \right|$

where λ_s is the s-dimensional Lebesgue measure, A(B;P) is the number of points in P that fall into B, and J is the set of s-dimensional intervals or boxes of the form

$\prod_{i=1}^s [a_i, b_i) = \{ \mathbf{x} \in \mathbf{R}^s : a_i \le x_i < b_i \} \,$

where $0 \le a_i < b_i \le 1$.

The star-discrepancy D^*_N(P) is defined similarly, except that the supremum is taken over the set J^* of intervals of the form

$\prod_{i=1}^s [0, u_i)$

where u_i is in the half-open interval [0, 1).

The two are related by

$D^*_N \le D_N \le 2^s D^*_N . \,$

Graphical examples

The points plotted below are the first 100, 1000, and 10000 elements in a sequence of the Sobol' type. For comparison, 10000 elements of a sequence of pseudorandom points are also shown. The low-discrepancy sequence was generated by TOMS algorithm 659. An implementation of the algorithm in Fortran is available from Netlib.

The first 100 points in a low-discrepancy sequence of the Sobol' type.

The first 1000 points in the same sequence. These 1000 comprise the first 100, with 900 more points.

The first 10000 points in the same sequence. These 10000 comprise the first 1000, with 9000 more points.

For comparison, here are the first 10000 points in a sequence of uniformly distributed pseudorandom numbers. Regions of higher and lower density are evident.

The Koksma–Hlawka inequality

Let Ī^s be the s-dimensional unit cube, Ī^s = [0, 1] × ... × [0, 1]. Let f have bounded variation V(f) on Ī^s in the sense of Hardy and Krause. Then for any x₁, ..., x_N in I^s = [0, 1) × ... × [0, 1),

$\left| \frac{1}{N} \sum_{i=1}^N f(x_i) - \int_{\bar I^s} f(u)\,du \right| \le V(f)\, D_N^* (x_1,\ldots,x_N).$

The Koksma-Hlawka inequality is sharp in the following sense: For any point set {x₁,...,x_N} in I^s and any $\epsilon>0$, there is a function f with bounded variation and V(f)=1 such that

$\left| \frac{1}{N} \sum_{i=1}^N f(x_i) - \int_{\bar I^s} f(u)\,du \right|>D_{N}^{*}(x_1,\ldots,x_N)-\epsilon.$

Therefore, the quality of a numerical integration rule depends only on the discrepancy D^*_N(x₁,...,x_N).

The formula of Hlawka-Zaremba

Let $D=\{1,2,\ldots,d\}$. For $\emptyset\neq u\subseteq D$ we write

$dx_u:=\prod_{j\in u} dx_j$

and denote by $(x_u,1)$ the point obtained from x by replacing the coordinates not in u by $1$. Then

$\frac{1}{N} \sum_{i=1}^N f(x_i) - \int_{\bar I^s} f(u)\,du= \sum_{\emptyset\neq u\subseteq D}(-1)^{|u|} \int_{[0,1]^{|u|}}{\rm disc}(x_u,1)\frac{\partial^{|u|}}{\partial x_u}f(x_u,1) dx_u.$

The $L^2$ version of the Koksma–Hlawka inequality

Applying the Cauchy-Schwarz inequality for integrals and sums to the Hlawka-Zaremba identity, we obtain an $L^2$ version of the Koksma–Hlawka inequality:

$\left|\frac{1}{N} \sum_{i=1}^N f(x_i) - \int_{\bar I^s} f(u)\,du\right|\le \|f\|_{d}\,{\rm disc}_{d}(\{t_i\}),$

where

${\rm disc}_{d}(\{t_i\})=\left(\sum_{\emptyset\neq u\subseteq D} \int_{[0,1]^{|u|}}{\rm disc}(x_u,1)^2 dx_u\right)^{1/2}$

and

$\|f\|_{d}=\left(\sum_{u\subseteq D} \int_{[0,1]^{|u|}} \left|\frac{\partial^{|u|}}{\partial x_u}f(x_u,1)\right|^2 dx_u\right)^{1/2}.$

The Erdős–Turán–Koksma inequality

It is computationally hard to find the exact value of the discrepancy of large point sets. The Erdős–Turán–Koksma inequality provides an upper bound.

Let x₁,...,x_N be points in I^s and H be an arbitrary positive integer. Then

$D_{N}^{*}(x_1,\ldots,x_N)\leq \left(\frac{3}{2}\right)^s \left( \frac{2}{H+1}+ \sum_{0<\|h\|_{\infty}\leq H}\frac{1}{r(h)} \left| \frac{1}{N} \sum_{n=1}^{N} e^{2\pi i\langle h,x_n\rangle} \right| \right)$

where

$r(h)=\prod_{i=1}^s\max\{1,|h_i|\}\quad\mbox{for}\quad h=(h_1,\ldots,h_s)\in\Z^s.$

The main conjectures

Conjecture 1. There is a constant c_s depending only on the dimension s, such that

$D_{N}^{*}(x_1,\ldots,x_N)\geq c_s\frac{(\ln N)^{s-1}}{N}$

for any finite point set {x₁,...,x_N}.

Conjecture 2. There is a constant c^'_s depending only on s, such that

$D_{N}^{*}(x_1,\ldots,x_N)\geq c'_s\frac{(\ln N)^{s}}{N}$

for at least one N for any infinite sequence x₁,x₂,x₃,....

These conjectures are equivalent. They have been proved for s ≤ 2 by W. M. Schmidt. In higher dimensions, the corresponding problem is still open. The best-known lower bounds are due to K. F. Roth.

The best-known sequences

Constructions of sequences are known such that

$D_{N}^{*}(x_1,\ldots,x_N)\leq C\frac{(\ln N)^{s}}{N}.$

where C is a certain constant, depending on the sequence. After Conjecture 2, these sequences are believed to have the best possible order of convergence. See also: van der Corput sequence, Halton sequences, Sobol sequences.

Lower bounds

Let s = 1. Then

$D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2N}$

for any finite point set {x₁, ..., x_N}.

Let s = 2. W. M. Schmidt proved that for any finite point set {x₁, ..., x_N},

$D_N^*(x_1,\ldots,x_N)\geq C\frac{\log N}{N}$

where

$C=\max_{a\geq3}\frac{1}{16}\frac{a-2}{a\log a}=0.023335\dots$

For arbitrary dimensions s > 1, K.F. Roth proved that

$D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2^{4s}}\frac{1}{((s-1)\log2)^\frac{s-1}{2}}\frac{\log^{\frac{s-1}{2}}N}{N}$

for any finite point set {x₁, ..., x_N}. This bound is the best known for s > 3.

Applications

• Integration
• Optimization
• Statistical sampling

References

• Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, ISBN 978-0-521-19159-3
• Kuipers, L.; Niederreiter, H. (2005), Uniform distribution of sequences, Dover Publications, ISBN 0-486-45019-8 
• Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5
• Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997, ISBN 3-540-62606-9
• William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, second edition 1992. ISBN 0-521-43108-5 (see Section 7.7 for a less technical discussion of low-discrepancy sequences)
• Quasi-Monte Carlo Simulations, http://www.puc-rio.br/marco.ind/quasi_mc.html

External links

• Collected Algorithms of the ACM (See algorithms 647, 659, and 738.)
• GNU Scientific Library Quasi-Random Sequences