Constructions of lowdiscrepancy sequences

There are some standard constructions of lowdiscrepancy sequences.
Contents
The van der Corput sequence
Main article: van der Corput sequenceLet
be the bary representation of the positive integer n ≥ 1, i.e. 0 ≤ d_{k}(n) < b. Set
Then there is a constant C depending only on b such that (g_{b}(n))_{n ≥ 1} satisfies
where D^{*}_{N} is the star discrepancy.
The Halton sequence
Main article: Halton sequenceThe Halton sequence is a natural generalization of the van der Corput sequence to higher dimensions. Let s be an arbitrary dimension and b_{1}, ..., b_{s} be arbitrary coprime integers greater than 1. Define
Then there is a constant C depending only on b_{1}, ..., b_{s}, such that sequence {x(n)}_{n≥1} is a sdimensional sequence with
The Hammersley set
Let b_{1},...,b_{s1} be coprime positive integers greater than 1. For given s and N, the sdimensional Hammersley set of size N is defined by
for n = 1, ..., N. Then
where C is a constant depending only on b_{1}, ..., b_{s−1}.
References
 QuasiMonte Carlo Simulations, http://www.pucrio.br/marco.ind/quasi_mc.html
Categories: Numerical analysis
 Quasirandomness
 Diophantine approximation
Wikimedia Foundation. 2010.
Look at other dictionaries:
Lowdiscrepancy 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