Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Categories: Numerical analysis | Random numbers | Number theory

Low-discrepancy sequence

(Redirected from Quasirandom)

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 numbers are used instead. The "quasi" modifier is used to denote more clearly that the numbers are not random, 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 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:

$\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₁, ..., 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.

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.

$D^*_N(P) = \sup_{B\in J^*} \left| \frac{A(B;P)}{N} - \lambda_s(B) \right|$

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

$\prod_{i=1}^s [0, u_i)$

where u_i 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)).$

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

$\left| \frac{1}{N} \sum_{i=1}^N f(x_i) - \int_{\bar I^s} f(u)\,du \right| \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₁,...,x_N in I^s and any

ε > 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_{\bar I^s} f(u)\,du \right|>D_{N}^{*}(x_1,\ldots,x_N)-\epsilon.$

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 Paul 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

$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 c_s depending only on s, such that

$D_{N}^{*}(x_1,\ldots,x_N)\geq c_s\frac{(\ln N)^{s-1}}{N}$

for any finite point set x₁,...,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'_s\frac{(\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, 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 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

$D_N^*(x_1,\ldots,x_N)\geq\frac{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,

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

Categories: Numerical analysis | Random numbers | Number theory

Science Fair Project Encyclopedia Contents Page

11-30-2008 18:11:33
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects