Halton sequence

256 points from a pseudorandom number source (top) compared with the first 256 points from the 2,3 Halton sequence (below). The Halton sequence covers the space more evenly. (red=1,..,10, blue=11,..,100, green=101,..,256)

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, consult that article for a precise definition.

Example of Halton sequence used to generate points in (0, 1) × (0, 1) in R²

Illustration of the first 8 points of the 2,3 Halton sequence

The Halton sequence is constructed according to a deterministic method that uses coprime numbers as its bases. 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

 ¹⁄₂,  ¹⁄₄,  ³⁄₄,  ¹⁄₈,  ⁵⁄₈,  ³⁄₈,  ⁷⁄₈,  ¹⁄₁₆,  ⁹⁄₁₆,...

Equivalently, the nth number of this sequence is the number n written in binary representation, inversed, and written after the decimal point. This is true for any base. As an example, to find the sixth element of the above sequence, we'd write 6 = 1*2² + 1*2¹ + 0*2⁰ = 110₂, which can be inverted and placed after the decimal point to give 0.011₂ = 0*2^-1 + 1*2^-2 + 1*2^-3 =  ³⁄₈. So the sequence above is the same as

0.1₂, 0.01₂, 0.11₂, 0.001₂, 0.101₂, 0.011₂, 0.111₂, 0.0001₂, 0.1001₂,...

To generate the sequence for 3, we divide the interval (0,1) in thirds, then ninths, twenty-sevenths, etc., which generates

 ¹⁄₃,  ²⁄₃,  ¹⁄₉,  ⁴⁄₉,  ⁷⁄₉,  ²⁄₉,  ⁵⁄₉,  ⁸⁄₉,  ¹⁄₂₇,...

When we pair them up, we get a sequence of points in a unit square:

( ¹⁄₂,  ¹⁄₃), ( ¹⁄₄,  ²⁄₃), ( ³⁄₄,  ¹⁄₉), ( ¹⁄₈,  ⁴⁄₉), ( ⁵⁄₈,  ⁷⁄₉), ( ³⁄₈,  ²⁄₉), ( ⁷⁄₈,  ⁵⁄₉), ( ¹⁄₁₆,  ⁸⁄₉), ( ⁹⁄₁₆,  ¹⁄₂₇).

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 16 pairs of points: ( ¹⁄₁₇,  ¹⁄₁₉), ( ²⁄₁₇,  ²⁄₁₉), ( ³⁄₁₇,  ³⁄₁₉) ... ( ¹⁶⁄₁₇,  ¹⁶⁄₁₉) 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. Another solution is using leaped Halton, just skipping points. If you use e.g. only each 409th point (also other prime numbers not used in the Halton core sequence are possible), then you can achieve significant improvements.

Implementation in pseudocode

FUNCTION (index, base)
BEGIN
    result = 0;
    f = 1;
    i = index;
    WHILE (i > 0) 
    BEGIN
        f = f / base;
        result = result + f * (i % base);
        i = FLOOR(i / base);
    END
    RETURN result;
END

See also

• Constructions of low-discrepancy sequences

References

• Kuipers, L.; Niederreiter, H. (2005), Uniform distribution of sequences, Dover Publications, p. 129, ISBN 0-486-45019-8
• Niederreiter, Harald (1992), Random number generation and quasi-Monte Carlo methods, SIAM, p. 29, ISBN 0-89871-295-5.
• Halton, J. (1964), Algorithm 247: Radical-inverse quasi-random point sequence, ACM, p. 701, doi:10.1145/355588.365104.