Low-discrepancy sequence Guide, Meaning , Facts, Information and Description

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.

The notion of uniformity is made precise as the discrepancy defined below. Roughly speaking, the discrepancy of a sequency 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 [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₁, ..., 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.

Table of contents

1 Definition of discrepancy 2 The Koksma-Hlawka inequality 3 The Erdős-Turan-Koksma inequality 4 The main conjectures 5 The best-known sequences 6 Lower bounds 7 References 8 External links

Definition of discrepancy

The Star-Discrepancy is defined as follows, using Niederreiter's notation.

where P is the set x₁, ..., 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

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

The Koksma Hlawka inequality is sharp in the following sense:

For any point set x₁,...,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₁,...,x_N).

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₁,...,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₁,...,x_N.

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

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, Niederreiter and Van der Corput) such that

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

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

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

where

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

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

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

This is an Article on Low-discrepancy sequence. Page Contains Information, Facts Details or Explanation Guide About Low-discrepancy sequence

	Web www.E-paranoids.com