QuasiRandom
Class Sobol

java.lang.Object
  QuasiRandom.LowDiscrepancySequence
      QuasiRandom.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() THE SOBOL POINTS

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

pp

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

Sobol

public Sobol(int dim)

Parameters:

dim - dimension of the Sobol sequence.

Method Detail

getName

public java.lang.String getName()

Description copied from class: LowDiscrepancySequence

Name of sequence.

Specified by:

getName in class LowDiscrepancySequence

gray

public static int gray(int n)

The Gray code of n.

restart

public void restart()

THE SOBOL POINTS

Overrides:

restart in class LowDiscrepancySequence

nextPoint

public double[] nextPoint()

The next Sobol point in the unit cube [0,1]^dim.

Specified by:

nextPoint in class LowDiscrepancySequence

main

public static void main(java.lang.String[] args)

Small test program, allocates a Sobol generator and prints several Sobol points.