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 FaureSequence 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 T:Extreme.Mathematics.LinearAlgebra.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 T:Extreme.Mathematics.LinearAlgebra.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 P:Extreme.Statistics.Random.RandomSequence.Capacity property specifies the maximum number of points
in the sequence. Other properties and methods implement the IEnumerator interface: M:Extreme.Statistics.Random.RandomSequence.MoveNext, M:Extreme.Statistics.Random.RandomSequence.Reset, and P:Extreme.Statistics.Random.RandomSequence.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 |
|---|
GeneralVector point = Vector.Create(8);
FaureSequence sequence1 = new FaureSequence(point, 10000);
|
| Visual Basic | Copy |
|---|
Dim point As GeneralVector = Vector.Create(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 |
|---|
FaureSequence sequence2 = new FaureSequence(8, 10000, true);
|
| Visual Basic | Copy |
|---|
Dim sequence2 As FaureSequence = New FaureSequence(8, 10000, True)
|
| C# | Copy |
|---|
double sum = 0.0;
foreach(GeneralVector v in sequence1)
{
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 |
|---|
Dim sum As Double = 0.0
For Each v As Vector In sequence1
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 |
|---|
GeneralVector point = Vector.Create(8);
HaltonSequence sequence3 = new HaltonSequence(point, 10000);
|
| Visual Basic | Copy |
|---|
Dim point As GeneralVector = Vector.Create(8)
Dim sequence3 As HaltonSequence = New HaltonSequence(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. Here is the same sequence again:
| C# | Copy |
|---|
HaltonSequence sequence4 = new HaltonSequence(8, 10000, true);
|
| Visual Basic | Copy |
|---|
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.