↑ arvau

Wikipedia / Low-discrepancy sequence

In mathematics, a low-discrepancy sequence is a sequence has a low discrepancy.

Roughly speaking, the discrepancy of a sequence is low if the proportion 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 equidistributed sequence. 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 quasirandom 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.

Applications

Quasirandom numbers have an advantage over pure random numbers in that they cover the domain of interest quickly and evenly.

Two useful applications are in finding the characteristic function of a probability density function, and in finding the derivative function of a deterministic function with a small amount of noise. Quasirandom numbers allow higher-order moments to be calculated to high accuracy very quickly.

Applications that don't involve sorting would be in finding the mean, standard deviation, skewness and kurtosis of a statistical distribution, and in finding the integral and global maxima and minima of difficult deterministic functions. Quasirandom numbers can also be used for providing starting points for deterministic algorithms that only work locally, such as Newton–Raphson iteration.

Quasirandom numbers can also be combined with search algorithms. With a search algorithm, quasirandom numbers can be used to find the mode, median, confidence intervals and cumulative distribution of a statistical distribution, and all local minima and all solutions of deterministic functions.

Low-discrepancy sequences in numerical integration

Various methods of numerical integration

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

is increased, but the point sets do not have minimal discrepancy. By using low-discrepancy sequences we aim for low discrepancy and no need for recomputations, but actually low-discrepancy sequences can only be incrementally good on discrepancy if we allow no recomputation.

Definition of discrepancy

The discrepancy is defined, using Niederreiter's

-dimensional Lebesgue measure-dimensional intervals or boxes of the form

.

The star-discrepancy is defined similarly, except that the supremum of rectangular boxes of the form

.

The two are related by

Note.

The Koksma–Hlawka inequality

-dimensional unit cube have bounded variation in the sense of Hardy,

The Koksma–Hlawka such that

.

The formula of Hlawka–Zaremba

the point obtained from x by replacing the coordinates not in u. Then

is the discrepancy function.

The L2 version of the Koksma–Hlawka inequality

Applying the Cauchy–Schwarz inequality version of the Koksma–Hlawka inequality:

where

and

discrepancy as criteria.

The Erdős–Turán–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.

be an arbitrary positive integer. Then

where

The main conjectures

Conjecture 1..

Conjecture 2.

.

by W. M. Schmidt. In higher dimensions, the corresponding problem is still open. The best-known lower bounds are due to Michael Lacey and collaborators.

Lower bounds

. Then

.

. W. M. Schmidt,

where

, K. F. Roth proved that

. Jozef Beck established a double log improvement of this result in three dimensions. This was improved by D. Bilyk and M. T. Lacey to a power of a single logarithm. The best known bound for s>2 is due D. Bilyk and M. T. Lacey and A. Vagharshakyan. depending on s

.

,

.

Construction of low-discrepancy sequences

Because any distribution of random numbers can be mapped onto a uniform distribution, and quasirandom numbers are mapped in the same way, this article only concerns generation of quasirandom numbers on a multidimensional uniform distribution.

is a certain constant, depending on the sequence. After Conjecture 2, these sequences are believed to have the best possible order of convergence. Examples below are the van der Corput sequence, the Halton sequences, and the Sobol’ sequences points from a low-discrepancy sequence generator may offer only a very minor accuracy improvement .

Random numbers

using:

even.

A second way to do it with the starting random numbers is to construct a random walk with offset 0.5 as in:

That is, take the previous quasirandom number, add 0.5 and the random number, and take the result modulo1.

For more than one dimension, Latin squares of the appropriate dimension can be used to provide offsets to ensure that the whole domain is covered evenly.

Additive recurrence

, the sequence

gives lower discrepancy than a sequence of independent uniform random numbers.

The discrepancy can be bounded by the approximation exponent, the following bound holds:

By the Thue–Siegel–Roth theorem, the approximation exponent of any irrational algebraic number above.

The recurrence relation above is similar to the recurrence relation used by a linear congruential generator, a poor-quality pseudorandom number generator:

For the low discrepancy additive recurrence above, a and m are chosen to be 1. Note, however, that this will not generate independent random numbers, so should not be used for purposes requiring independence.

with lowest discrepancy is the fractional part of the golden ratio:

Another value that is nearly as good is the fractional part of the silver ratio, which is the fractional part of the square root of 2:

In more than one dimension, separate quasirandom numbers are needed for each dimension. A convenient set of values that are used, is the square roots of primes from two up, all taken modulo 1:

However, a set of values based on the generalised golden ratio has been shown to produce more evenly distributed points.

The list of pseudorandom number generators lists methods for generating independent pseudorandom numbers. Note) other point set generators can offer much lower discrepancies.

van der Corput sequence

Let

. Set

satisfies

is the star discrepancy.

Halton sequence

The Halton sequence is a natural generalization of the van der Corput sequence to higher dimensions. Let s be an arbitrary dimension and b1, ..., bs be arbitrary coprime integers greater than 1. Define

Then there is a constant C depending only on b1, ..., bs, such that sequence {x(n)}n≥1 is a s-dimensional sequence with

Hammersley set

be coprime-dimensional Hammersley is defined by

. Then

.

Note, most low-discrepancy point set generators deliver at least near-optimum discrepancies.

Sobol sequence

called direction numbers. The bits of the Gray code take the exclusive or.

Poisson disk sampling

Poisson disk sampling is popular in video games to rapidly place objects in a way that appears random-looking but guarantees that every two points are separated by at least the specified minimum distance. This does not guarantee low discrepancy (as e. g. Sobol’), but at least a significantly lower discrepancy than pure random sampling. The goal of these sampling patterns is based on frequency analysis rather than discrepancy, a type of so-called "blue noise" patterns.

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. An implementation of the algorithm in Fortran is available from Netlib.

See also

Notes

References