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 randomfor many purposes. They were first introduced in 1960 and are an example of a quasi-random numbersequence. They generalise the one-dimensional van der Corput sequences.
Example of Halton sequence used to generate points in (0, 1) × (0, 1) in R2
The Halton sequence is constructed according to a deterministic method that uses a
prime numberas its base. As a simple example, let's take one dimension of the Halton sequence to be based on 2 and the other on 3. To generate the sequence for 2, we start by dividing the interval (0,1) in half, then in fourths, eighths, etc, which generates
: 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16,...
and to generate the sequence for 3, we divide the interval (0,1) in thirds, then ninths, twenty-sevenths, etc, which generates
: 1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9, 1/27,...
When we pair them up, we get a sequence of points in a unit square:
: (1/2, 1/3), (1/4, 2/3), (3/4, 1/9), (1/8, 4/9), (5/8, 7/9), (3/8, 2/9), (7/8, 5/9), (1/16, 8/9), (9/16, 1/27).
Even though standard Halton sequences perform very well in low dimensions, correlation problems have been noted between sequences generated from higher primes. For example if we started with the primes 17 and 19, the first 17 pairs of points would have perfect
linear correlation. To avoid this, it is common to drop the first 20 entries, or some other predetermined number depending on the primes chosen. In order to deal with this problem, various other methods have been proposed; one of the most prominent solutions is the scrambled Halton sequence, which uses permutations of the coefficients used in the construction of the standard sequence.
Constructions of low-discrepancy sequences
* [http://orion.math.iastate.edu/reu/2001/voronoi/halton_sequence.html A better method for generating the Halton]
Wikimedia Foundation. 2010.
Look at other dictionaries:
Halton — may refer to: Places in the United Kingdom * Halton, Buckinghamshire * Halton, Cheshire * Halton (borough), Cheshire **Halton (UK Parliament constituency) * Halton, Lancashire * Halton, Northumberland * Halton, Leeds, West Yorkshire * Halton East … Wikipedia
Halton Arp — Londres en octobre 2000 Naissance 21 mars 1927 New York ( … Wikipédia en Français
Random sequence — A random sequence is a kind of stochastic process. In short, a random sequence is a sequence of random variables. Random sequences are essential in statistics. The statistical analysis of any experiment usually begins with the words let X 1,...,… … Wikipedia
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
Constructions of low-discrepancy sequences — There are some standard constructions of low discrepancy sequences. Contents 1 The van der Corput sequence 2 The Halton sequence 3 The Hammersley set 4 References … Wikipedia
List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… … Wikipedia
The World Is Not Enough — This article is about the 1999 film. For other uses, see The World Is Not Enough (disambiguation). The World Is Not Enough … Wikipedia
cosmos — /koz meuhs, mohs/, n., pl. cosmos, cosmoses for 2, 4. 1. the world or universe regarded as an orderly, harmonious system. 2. a complete, orderly, harmonious system. 3. order; harmony. 4. any composite plant of the genus Cosmos, of tropical… … Universalium
Two Pints of Lager and a Packet of Crisps — For the song by Splodgenessabounds, see Two Pints Of Lager And A Packet Of Crisps Please. Two Pints of Lager and a Packet of Crisps … Wikipedia
Origin of the Oak Ridges Moraine — For general context, see Oak Ridges Moraine. The Oak Ridges Moraine is a geological landform that runs east west across south central Ontario, Canada. It developed about 12,000 years ago, during the Wisconsin glaciation in North America. A… … Wikipedia