Constructions of low-discrepancy sequences

There are some standard constructions of low-discrepancy sequences.

The van der Corput sequence

Let

$n=\sum_{k=0}^{L-1}d_k(n)b^k$

be the b-ary representation of the positive integer n ≥ 1, i.e. 0 ≤ dk(n) < b. Set

$g_b(n)=\sum_{k=0}^{L-1}d_k(n)b^{-k-1}.$

Then there is a constant C depending only on b such that (gb(n))n ≥ 1 satisfies

$D^*_N(g_b(1),\dots,g_b(N))\leq C\frac{\log N}{N}.$

where D*N is the star discrepancy.

The Halton sequence

First 256 points of the (2,3) 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

$x(n)=(g_{b_1}(n),\dots,g_{b_s}(n)).$

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

$D^*_N(x(1),\dots,x(N))\leq C'\frac{(\log N)^s}{N}.$

The Hammersley set

2D Hammersley set of size 256

Let b1,...,bs-1 be coprime positive integers greater than 1. For given s and N, the s-dimensional Hammersley set of size N is defined by

$x(n)=(g_{b_1}(n),\dots,g_{b_{s-1}}(n),\frac{n}{N})$

for n = 1, ..., N. Then

$D^*_N(x(1),\dots,x(N))\leq C\frac{(\log N)^{s-1}}{N}$

where C is a constant depending only on b1, ..., bs−1.

References

Wikimedia Foundation. 2010.

Look at other dictionaries:

• 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… …   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

• 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

• 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

• 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

• List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   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

• biblical literature — Introduction       four bodies of written works: the Old Testament writings according to the Hebrew canon; intertestamental works, including the Old Testament Apocrypha; the New Testament writings; and the New Testament Apocrypha.       The Old… …   Universalium

• physical science, principles of — Introduction       the procedures and concepts employed by those who study the inorganic world.        physical science, like all the natural sciences, is concerned with describing and relating to one another those experiences of the surrounding… …   Universalium