# Low-discrepancy sequence

This article needs attention from an expert in Mathematics. |

In mathematics, a **low-discrepancy sequence** is a sequence with the property that for all values of *N*, its subsequence *x*_{1}, ..., *x*_{N} has a low discrepancy, as defined below.

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.

Roughly speaking, the discrepancy of a sequence is low if the number 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 uniform distribution. 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).

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

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**, 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 another which is the discrepancy of the set *x*_{1}, ..., *x*_{N}.
The Koksma-Hlawka inequality is stated below.

It is convenient to construct the set *x*_{1}, ..., *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 Star-Discrepancy is defined as follows, using Niederreiter's notation.

where *P* is the set *x*_{1}, ..., *x*_{N},
λ_{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 intervals of the form

where *u*_{i} is in the half-open interval [0, 1).
Therefore

where the discrepancy function is defined by

## 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,
described by P. Bratley and B.L. Fox in *ACM Transactions on Mathematical Software*, vol. 14, no. 1, pp 88--100.
An implementation of the algorithm in Fortran may be downloaded from Netlib, URL: http://www.netlib.org/toms/659

## 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*_{1}, ..., *x*_{N}
in *I*^{s} =
[0, 1) × ... ×
[0, 1),

The Koksma-Hlawka inequality is sharp in the following sense:

For any point set *x*_{1},...,*x*_{N} in *I*^{s} and any

- ,

there is a function *f* with bounded variation and *V(f)=1* such that

Therefore, the quality of a numerical integration rule depends only on the discrepancy D^{*}_{N}(*x*_{1},...,*x*_{N}).

## The formula of Hlawka-Zaremba

Let . For we write

and denote by the point obtained from by replacing the coordinates not in by . Then

## The version of the Koksma-Hlawka inequality

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

where

and

## The Erdős-Turan-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*_{1},...,*x*_{N} be points in *I*^{s} and *H* be an arbitrary positive integer. Then

where

## The main conjectures

**Conjecture 1.** There is a constant *c*_{s} depending only on *s*, such that

for any finite point set *x*_{1},...,*x*_{N}.

**Conjecture 2.** There is a constant *c*^{'}_{s} depending only on *s*, such that

for any infinite sequence *x*_{1},*x*_{2},*x*_{3},....

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 (due to Faure, Halton, Hammersley, Sobol', Niederreiter and van der Corput) such that

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: Halton sequences.

## Lower bounds

Let *s* = 1. Then

for any finite point set *x*_{1}, ..., *x*_{N}.

Let *s* = 2. W. M. Schmidt proved that for any finite point set *x*_{1}, ..., *x*_{N},

where

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

for any finite point set *x*_{1}, ..., *x*_{N}.
This bound is the best known for *s* > 3.

## Applications

## References

- 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)*

## External links

- Collected Algorithms of the ACM
*(See algorithms 647, 659, and 738.)*