Halton sequences
Encyclopedia
In statistics
, Halton sequences are sequence
s 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 sequence
s.
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
and 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 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.
BEGIN
result = 0;
f = 1 / base;
i = index;
WHILE (i > 0)
BEGIN
result = result + f * (i % base);
i = FLOOR(i / base);
f = f / base;
END
RETURN result;
END
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, Halton sequences are sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
s used to generate points in space for numerical methods such as Monte Carlo simulations. Although these sequences are deterministic
Deterministic system (mathematics)
In mathematics, a deterministic system is a system in which no randomness is involved in the development of future states of the system. A deterministic model will thus always produce the same output from a given starting condition or initial state.-Examples:...
they are of low discrepancy
Low-discrepancy sequence
In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN has a 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 sequence
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...
s.
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 numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
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
- , , , , , , , , ,...
and 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 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.
Implementation in Pseudo Code
FUNCTION (index, base)BEGIN
result = 0;
f = 1 / base;
i = index;
WHILE (i > 0)
BEGIN
result = result + f * (i % base);
i = FLOOR(i / base);
f = f / base;
END
RETURN result;
END