The Classical Examples of Low-Discrepancy Sequences

Van der Corput and Halton Sequence

Let an arbitrary integer and the residue system modulo . The radical inverse function in base is defined as

,     ,

where is the -adic expansion of the integer . For every integer , the Van der Corput sequence in base is the one-dimensional sequence defined as The generalized Van der Corput sequence is obtained by permuting the digits in the -adic expansion.

For maximal performance, the Van der Corput sequence is implemented using dynamic programming.

The first 10 sequence elements of the Van der Corput sequence in base 7, as rational numbers.

To evaluate the sequence numerically, just enter the basis as a real number.

The uniformity (i.e. discrepancy) of the Van der Corput sequence can be reduced further by permuting the digits in the digits expansion.

The Halton sequence and the permuted Halton sequence are the multi-dimensional analogons. The bases must be relatively prime.

Hammersley Point Set

The -element Hammersley point set in the bases is defined for all as .

The Weyl Sequence

A prominent record holder is given by the -sequence, which is a special type of a Weyl sequence. The -th element of the Weyl sequence generated by is given by , where denotes the fractional part. Again, Mathematica offers symbolic as well as numeric calculation.

Comparision with Pseudo-Random Numbers

Low discrepancy sequences are designed to be as uniform as possible. We compare the Halton sequence to ordinary pseudo-random sequences.

On the other hand ordinary pseudo-random numbers are visually less uniformly distributed and show clustering.

The statistical distribution properties of the Halton sequence and pseudo-random sequences compared:

The exact values of the uniform distribution:

Mean	Variance	Skewness	Kurtosis
		0
0.5`	0.0833333333333333214`	0	1.8`

Other Constructions

Other classical low-discrepancy sequences are those of Faure and Sobol. We refer to the literature. Also, there is the construction of low-discrepancy sequences based on so called -nets and -sequences and the digital method for their construction. This approach was manly developed by H. Niederreiter. We will investigate this method in the next chapter.

Converted by Mathematica November 18, 1998