Low-discrepancy Sequence

In Mathematics , a low-discrepancy sequence is a Sequence with the property that for all ''N'', the subsequence ''x''₁, ..., ''x''_''N'' is almost uniformly distributed (in a sense to be made precise), and ''x''₁, ..., ''x''_''N''+1 is almost uniformly distributed as well. The reader may wish to consider this Illustration Of A Low-discrepancy Sequence . Low-discrepancy sequences are also called quasi-random or '''sub-random''' sequences, due to their use in situations similar to those when Pseudorandom or Random Number s are used instead. The "quasi" modifier is used to denote more clearly that the numbers are not random (and to differentiate them from pseudorandomness, which uses different assumptions), but have useful properties similar to Randomness in certain applications such as the Quasi-Monte Carlo Method . The notion of ''uniformity'' is made precise as the discrepancy defined below. Roughly speaking, the discrepancy of a sequence is low if the number of points falling into a set ''B'' is close to the number one would expect from the measure of ''B''. At least three methods of Numerical Integration can be phrased as follows. Given a set ''x''₁, ..., ''x''_''N'' in the interval {Link without Title} , approximate the integral of a function ''f'' as the average of the function evaluated at those points: : $\int_0^1 f(u)\,du \approx rac{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 Pseudorandom ly) 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''₁, ..., ''x''_''N''. The Koksma-Hlawka inequality is stated below. 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 Star-Discrepancy is defined as follows, using Niederreiter's notation. _N(P) = \sup_{B\in J^---}
	D^ N(P)	\{ m disc}\_\infty
	: <math> \left Rac{1}{N} \sum {i	1}^N f(x_i)
	\left Rac{1}{N} \sum {i	1}^N f(x_i)

\leftRac{1}{N} \sum {i 1}^N f(x_i)

\f\ {d} \left(\sum_{u\subseteq D}

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

for any finite point set ''x''₁,...,''x''_N.

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

}(x_1,\ldots,x_N)\geq c'_srac{(\ln N)^{s}}{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 (due to Faure, Halton, Hammersley , Sobol, Niederreiter and van der Corput) such that

:

}(x_1,\ldots,x_N)\leq Crac{(\ln N)^{s}}{N}.

where ''C'' is a certain constant, depending of 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

:

(x_1,\ldots,x_N)\geqrac{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'',

:

(x_1,\ldots,x_N)\geq Crac{\log N}{N}

where

:

C=\max_{a\geq3}rac{1}{16}rac{a-2}{a\log a}=0.02333...

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

:

(x_1,\ldots,x_N)\geqrac{1}{2^{4s}}rac{1}{((s-1)\log2)^rac{s-1}{2}}rac{\log^{rac{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

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.)''

	CATEGORIES ABOUT LOW-DISCREPANCY SEQUENCE

	numerical analysis

	quasirandomness

	diophantine approximation

	sequences

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Low-discrepancy Sequence