Low-discrepancy sequence


Low-discrepancy sequence

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.

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

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

: 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, 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 "discrepancy" of a sequence ("x""i") is defined, using Niederreiter's notation, as

: D_N(P) = sup_{Bin J} left| frac{A(B;P)}{N} - lambda_s(B) ight|

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 "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,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] &times; ... &times; [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) &times; ... &times; [0, 1),: left| frac{1}{N} sum_{i=1}^N f(x_i) - int_{ar I^s} f(u),du ight| 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"1,...,"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_{ar I^s} f(u),du ight|>D_{N}^{*}(x_1,ldots,x_N)-epsilon.

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 D={1,2,ldots,d}. For emptyset eq usubseteq D wewrite:dx_u:=prod_{jin u} dx_jand denote by (x_u,1) the point obtained from x by replacing thecoordinates not in u by 1.Then:frac{1}{N} sum_{i=1}^N f(x_i) - int_{ar I^s} f(u),du=sum_{emptyset eq usubseteq D}(-1)^int_{ [0,1] ^{|u|{ m 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 sumsto the Hlawka-Zaremba identity, we obtainan L^2 version of the Koksma-Hlawka inequality::left|frac{1}{N} sum_{i=1}^N f(x_i) - int_{ar I^s} f(u),du ight|le|f|_{d},{ m disc}_{d}({t_i}),where:{ m disc}_{d}({t_i})=left(sum_{emptyset eq usubseteq D}int_{ [0,1] ^{|u|{ m disc}(x_u,1)^2 dx_u ight)^{1/2}and:|f|_{d}=left(sum_{usubseteq D}int_{ [0,1] ^{|u|left|frac{partial^{|u|{partial x_u}f(x_u,1) ight|^2 dx_u ight)^{1/2}.

The Erds-Turan-Koksma inequality

It is computationally hard to find the exact value of the discrepancy of large point sets. The Erds-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

:D_{N}^{*}(x_1,ldots,x_N)leqleft(frac{3}{2} ight)^sleft(frac{2}{H+1}+sum_{0<|h|_{infty}leq H}frac{1}{r(h)}left
frac{1}{N}sum_{n=1}^{N} e^{2pi ilangle h,x_n angle} ight
ight)

where

:r(h)=prod_{i=1}^smax{1,|h_i|}quadmbox{for}quad h=(h_1,ldots,h_s)in^s.

The main conjectures

Conjecture 1. There is a constant "c"s depending only on "s", such that

:D_{N}^{*}(x_1,ldots,x_N)geq c_sfrac{(ln N)^{s-1{N}

for any finite point set "x"1,...,"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'_sfrac{(ln N)^{s{N}

for any infinite sequence "x"1,"x"2,"x"3,....

These conjectures are equivalent. They have been proved for "s" &le; 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 Cfrac{(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)geqfrac{1}{2N}

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",

:D_N^*(x_1,ldots,x_N)geq Cfrac{log N}{N}

where

:C=max_{ageq3}frac{1}{16}frac{a-2}{alog a}=0.02333...

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

:D_N^*(x_1,ldots,x_N)geqfrac{1}{2^{4sfrac{1}{((s-1)log2)^frac{s-1}{2frac{log^{frac{s-1}{2N}{N}

for any finite point set "x"1, ..., "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)"
* "Quasi-Monte Carlo Simulations", http://www.puc-rio.br/marco.ind/quasi_mc.html

External links

* [http://www.acm.org/calgo/contents/ Collected Algorithms of the ACM] "(See algorithms 647, 659, and 738.)"


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Constructions of low-discrepancy sequences — There are some standard constructions of low discrepancy sequences. Contents 1 The van der Corput sequence 2 The Halton sequence 3 The Hammersley set 4 References …   Wikipedia

  • Discrepancy function — A discrepancy function is a mathematical function which describes how closely a structural model conforms to observed data. Larger values of the discrepancy function indicate a poor fit of the model to data. In general, the parameter estimates… …   Wikipedia

  • Equidistributed sequence — In mathematics, a bounded sequence {s1, s2, s3, …} of real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that interval. Such sequences are… …   Wikipedia

  • Van der Corput sequence — A van der Corput sequence is a low discrepancy sequence over the unit interval first published in 1935 by the Dutch mathematician J. G. van der Corput. It is constructed by reversing the base n representation of the sequence of natural numbers (1 …   Wikipedia

  • Halton sequence — In statistics, Halton sequences are sequences used to generate points in space for numerical methods such as Monte Carlo simulations. Although these sequences are deterministic they are of low discrepancy, that is, appear to be random for many… …   Wikipedia

  • Monte Carlo methods in finance — Monte Carlo methods are used in finance and mathematical finance to value and analyze (complex) instruments, portfolios and investments by simulating the various sources of uncertainty affecting their value, and then determining their average… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Quasi-Monte Carlo method — In numerical analysis, a quasi Monte Carlo method is a method for the computation of an integral (or some other problem) that is based on low discrepancy sequences. This is in contrast to a regular Monte Carlo method, which is based on sequences… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Quasi-Monte Carlo methods in finance — High dimensional integrals in hundreds or thousands of variables occur commonly in finance. These integrals have to be computed numerically to within a threshold epsilon. If the integral is of dimension d then in the worst case, where one has a… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.