Class Sobol

  extended byQuasiRandom.LowDiscrepancySequence
      extended byQuasiRandom.Sobol

public class Sobol
extends LowDiscrepancySequence

Generator for the Sobol sequence. Uses the Gray code counter and bitwise operations for very fast point generation.

Use N=2^n-1, n=1,2,... points for QMC integration. At N=2^n-1 the Gray code counter G(k) is in sync with the integer sequence k=1,2,... again, that is { G(1),...,G(N) }={ 1,...,N }.

Dimension: the Sobol generator is implemented only in dimension at most 300. The current implementation relies on primitive polynomials and initialization numbers from the book [J]: Monte Carlo Methods in Finance by Peter Jaeckel, Wiley, ISNB 047149741X. The CD sold with the book contains millions of primitive polynomials allowing you to extend the generator to millions of dimensions.

If the dimension is small low discrepancy sequences are significantly better Monte Carlo integrators than uniform sequences while this advantage seems to fade as the dimension increases at least if the number N of points is restricted to values that are realistic in applications.

This would argue that we apply the Sobol sequence to a small number of important dimensions while driving the remaining dimensions with a uniform sequence. On the other hand [J] presents evidence that the Sobol sequence keeps up with the uniform sequence at any number N of points even in high dimensions if the initialization numbers are chosen properly.

In this regard it should be noted that even the best uniform random number generator, the Mersenne Twister is only known to deliver an equidistributed sequence up to dimension 623. If the sequence is not equidistributed we do not know wether the Monte Carlo integral converges to the true integral as the number N of points inreases to infinity. Low discrepancy sequences on the other hand are equidistributed in every dimension and so the Monte Carlo integral is guarenteed to converge to the true value of the integral.

The reader is advised to consult [J] for a detailed description of techniques to reduce effective dimensionality and much additional source code related to Monte Carlo simulation. It is an excellent reference on the topic.

Field Summary
static int[][] pp
          The list pp of primitive polynomials, pp[j] is the array of encodings n of primitive polynomials of degree j+1.
Constructor Summary
Sobol(int dim)
Method Summary
 java.lang.String getName()
          Name of sequence.
static int gray(int n)
          The Gray code of n.
static void main(java.lang.String[] args)
          Small test program, allocates a Sobol generator and prints several Sobol points.
 double[] nextPoint()
          The next Sobol point in the unit cube [0,1]^dim.
 void restart()
Methods inherited from class QuasiRandom.LowDiscrepancySequence
L2_discrepancy, L2_discrepancy, nextPoint, nextQuasiNormalVector, projectionPlot
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail


public static final int[][] pp
The list pp of primitive polynomials, pp[j] is the array of encodings n of primitive polynomials of degree j+1. The polynomial p(x)=1 of degree zero is dealt with separately

Constructor Detail


public Sobol(int dim)
dim - dimension of the Sobol sequence.
Method Detail


public java.lang.String getName()
Description copied from class: LowDiscrepancySequence
Name of sequence.

Specified by:
getName in class LowDiscrepancySequence


public static int gray(int n)
The Gray code of n.


public void restart()

restart in class LowDiscrepancySequence


public double[] nextPoint()
The next Sobol point in the unit cube [0,1]^dim.

Specified by:
nextPoint in class LowDiscrepancySequence


public static void main(java.lang.String[] args)
Small test program, allocates a Sobol generator and prints several Sobol points.