User's Guide

Up: Random Numbers Next: Random Enumerators Previous: Random Number Generators Contents

Quasi-random Sequences

Quasi-random sequences, also called low discrepancy sequences, are sequences of vectors that progressively cover a multi-dimensional space with points that are uniformly distributed. They are used in quasi-Monte Carlo simulations, in the evaluation of multi-dimensional integrals, and in global optimimization. The Extreme Optimization Statistics Library for .NET contains classes that implement two algorithms that generate such sequences. These classes reside in the Extreme.Statistics.Random namespace.

Using Quasi-random Sequences

All classes that implement quasi-random sequences inherit from the RandomSequence class. This class implements the IEnumerator interface. The current value is of type GeneralVector.

Traditionally, enumerators return a new instance on each iteration. For some scenarios where a large number of medium-size objects must be created, this can lead to serious performance degradation. For this reason, the quasi-random sequence classes let you reuse a single GeneralVector object to hold the current point in the sequence. At each iteration, the coordinates of the new point are copied into this vector. If you choose, you can still let the sequence return a new GeneralVector instance for each point.

You must specify the maximum number of points you wish to generate, which is called the capacity. This value must be specified as a parameter to the constructor.

All quasi-random sequence classes share a number of properties and methods. The Capacity property specifies the maximum number of points in the sequence. Other properties and methods implement the IEnumerator interface: MoveNext, Reset, and Current.

Because the quasi-random sequence classes implement IEnumerator, you can use the objects in a foreach loop.

There are several types of quasi-random sequences. They all share the property that they are less random than a sequence of vectors generated from random number generators. However, this is often an advantage for tasks such as approximating integrals in higher dimensions, and in global optimization. This is because low discrepancy sequences tend to sample space "more uniformly" than random numbers. Algorithms that use such sequences may have superior convergence over algorithms that use completely random vectors.

Fauré Sequences

The best known algorithm for generating quasi-random sequences is due to the French mathematician Henri Faur. Faur sequences are popular in mathematical finance simulations.

The FaureSequence class implements a Faur sequence. It has two constructors. The first constructor takes a GeneralVector that is to contain the points, and an integer that specifies the capacity. This creates a sequence of the specified capacity whose results will be returned in the specified vector. The dimension of the sequence is the same as the length of the vector.

C#	Copy Code
GeneralVector point = new GeneralVector(8); FaureSequence sequence1 = new FaureSequence(point, 10000);

Visual Basic	Copy Code
Dim point As GeneralVector = New GeneralVector(8) Dim sequence1As FaureSequence = New FaureSequence(point, 10000)

The second constructor takes three parameters. The first is an integer that specifies the dimension. The second is an integer that specifies the capacity. The third and last parameter is a boolean value that specifies whether a new GeneralVector instance should be returned for every point in the sequence.

C#	Copy Code
FaureSequence sequence2 = new FaureSequence(8, 10000, true);

Visual Basic	Copy Code
Dim sequence2 As FaureSequence = New FaureSequence(8, 10000, True)

The following example uses the above sequence to approximate an 8-dimensional integral:

C#	Copy Code
double sum = 0.0; foreach(GeneralVector v in sequence1) { // Evaluate the integrand: double functionValue = 1.0; for(int i = 0; i < v.Length; i++) functionValue = Math.Abs(4.0v[i]-2.0); sum += functionValue; } Console.WriteLine("Estimate: {0,8:F4}", sum / sequence1.Capacity);

Copy Code

double sum = 0.0;
foreach(GeneralVector v in sequence1)
{
    // Evaluate the integrand:
    double functionValue = 1.0;
    for(int i = 0; i < v.Length; i++)
        functionValue *= Math.Abs(4.0*v[i]-2.0);
    sum += functionValue;
}
Console.WriteLine("Estimate: {0,8:F4}", sum / sequence1.Capacity);

Visual Basic	Copy Code
Dim sum As Double = 0.0 For Each v As Vector In sequence1 ' Evaluate the integrand: Dim functionValue As Double = 1.0 For i As Integer = 0 To dimension - 1 functionValue = Math.Abs(4.0 v(i) - 2.0) Next sum += functionValue Next Console.WriteLine("Estimate: {0,8:F4}", sum / sequence1.Capacity)

Visual Basic

Copy Code

Dim sum As Double = 0.0
For Each v As Vector In sequence1
    ' Evaluate the integrand:
    Dim functionValue As Double = 1.0
    For i As Integer = 0 To dimension - 1
        functionValue *= Math.Abs(4.0 * v(i) - 2.0)
    Next
    sum += functionValue
Next
Console.WriteLine("Estimate: {0,8:F4}", sum / sequence1.Capacity)

Halton Sequences

A Halton sequence in n dimensions actually consists of n separate sequences of numbers. Every sequence is generated from a different prime number. It has been used successfully for numerical integration in multiple dimensions.

A Halton sequence works very well for low-dimensional spaces. For higher-dimensional spaces (20 or more dimensions) the initial elements can be very poorly distributed over the space. Moreover, some correlation patterns have been observed for larger dimensions involving larger prime numbers, making the Halton sequence relatively unsuitable for higher dimensions.

Halton sequences are implemented by the HaltonSequence class implements a Halton sequence. It has two constructors. The first constructor takes a GeneralVector that is to contain the points, and an integer that specifies the capacity. This creates a sequence of the specified capacity whose results will be returned in the specified vector. The dimension of the sequence is the same as the length of the vector. The following constructs a Halton sequence in 8 dimensions with 10,000 points:

C#	Copy Code
GeneralVector point = new GeneralVector(8); HaltonSequence sequence3 = new HaltonSequence(point, 10000);

Visual Basic	Copy Code
Dim point As GeneralVector = New GeneralVector(8) Dim sequence3 As HaltonSequence = New HaltonSequence(point, 10000)

C#	Copy Code
HaltonSequence sequence4 = new HaltonSequence(8, 10000, true);

Visual Basic	Copy Code
Dim sequence4 As HaltonSequence = New HaltonSequence(8, 10000, True)

In the above example, a new vector instance will be returned for every new point in the sequence.

References

Henri Fauré, Discrepance de suites associees a un systeme de numeration (en dimension s), Acta Arithmetica, Volume XLI, 1982, pages 337-351.

J.H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numerische Mathematik, Volume 2, 1960, pages 84-90.

J.H. Halton and G.B. Smith, Algorithm 247: Radical-Inverse Quasi-Random Point Sequence, Communications of the ACM, Volume 7, 1964, pages 701-702.