Halton sequence
From Wikipedia, the free encyclopedia
In statistics, Halton sequences are sequences used to generate points in space. Points generated using a Halton sequence are nearly uniformly distributed and appear to be random, although they are constructed deterministically. They were first introduced in 1960 and are an example of a quasi-random number sequence. They were designed mainly for use in Monte Carlo simulations of integrals that do not have a closed-form expression in order to achieve variance reduction.
[edit] Example of Halton sequence used to generate points in 
in 
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, 3/8, 5/8, 7/8, 1/16, 3/16,...
and to generate the sequence for 3, we divide the interval (0,1) in thirds, then ninths, twenty-sevents, etc, which generates
- 1/3, 2/3, 1/9, 2/9, 4/9, 5/9, 7/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, 2/9), (3/8, 4/9), (5/8, 5/9), (7/8, 7/9), (1/16, 8/9), (3/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.
