Low-discrepancy sequence
In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN 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 x1, ..., xN in the interval , approximate the integral of a function f as the average of the function evaluated at those points:
If the points are chosen as xi = 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 x1, ..., xN.
The Koksma-Hlawka inequality is stated below.
It is convenient to construct the set x1, ..., xN 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 x1, ..., xN,
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 ui is in the half-open interval [0, 1).
Therefore
D^*_N(P) =\|{\rm disc}\|_\infty
where the discrepancy function is defined by
{\rm disc}(y)=\frac{A([0,y);P)}{N}-\lambda_s([0,y)).

# 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: 

# The Koksma-Hlawka inequality
Let Is be the s-dimensional unit cube, 
Is =   ...  .
Let f have bounded variation V(f) on Is in the sense of Hardy and Krause.
Then for any x1, ..., xN 
in Is = 
The Koksma-Hlawka inequality is sharp in the following sense:
For any point set x1,...,xN in Is and any
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)
Therefore, the quality of a numerical integration rule depends only on the discrepancy D*N(x1,...,xN).

# 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)
\sum_{\emptyset\neq u\subseteq D}(-1)^{|u|}
\int_{^{|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)
\|f\|_{d}\,{\rm disc}_{d}(\{t_i\}),
where
{\rm disc}_{d}(\{t_i\})=\left(\sum_{\emptyset\neq u\subseteq D}
\int_{^{|u|}}{\rm disc}(x_u,1)^2 dx_u\right)^{1/2}
and
\|f\|_{d}=\left(\sum_{u\subseteq D}
\int_{^{|u|}}
\left|\frac{\partial^{|u|}}{\partial x_u}f(x_u,1)\right|^2 dx_u\right)^{1/2}.

# The Erdos-Turan-Koksma inequality
It is computationally hard to find the exact value of the discrepancy of large point sets. The Erdos-Turan-Koksma inequality provides an upper bound.
Let x1,...,xN be points in Is 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 cs depending only on s, such that
for any finite point set  x1,...,xN.
Conjecture 2.  There is a constant c's depending only on s, such that
for any infinite sequence  x1,x2,x3,....
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
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: Halton sequences.

# Lower bounds
Let s = 1. Then
D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2N}
for any finite point set x1, ..., xN.
Let s = 2. W. M. Schmidt proved that for any finite point set x1, ..., xN,
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.02333...
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 x1, ..., xN.
This bound is the best known for s > 3.

# Applications
- Integration
- Optimization
- Statistical sampling