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 purposes. They were first introduced in 1960 and are an example of a quasi-random number sequence. 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 number as 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.

See also

*Constructions of low-discrepancy sequences

References

*
*.

External links

* [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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.