com.imsl.stat

Class FaureSequence

java.lang.Object

com.imsl.stat.FaureSequence

All Implemented Interfaces:

RandomSequence, Serializable, Cloneable

public class FaureSequence
extends Object
implements Serializable, RandomSequence, Cloneable

Generates the low-discrepancy Faure sequence.

Discrepancy measures the deviation from uniformity of a point set.

The discrepancy of the point set $x_1,\ldots,x_n \in [0,1]^d,\, d \ge 1$, is $$D_n^{(d)} = \sup_E \left| \frac{A(E;n)}{n} - \lambda(E) \right|,$$ where the supremum is over all subsets of $[0,1]^d$ of the form $$E = \left[0,t_1\right) \times \cdots \times \left[0,t_d\right), \,\, 0 \le t_j \le 1, \, 1 \le j \le d,$$ $\lambda$ is the Lebesque measure, and A(E;n) is the number of the $x_j$ contained in E.

The sequence $x_1, x_2, \ldots$ of points in $[0,1]^d$ is a low-discrepancy sequence if there exists a constant c(d), depending only on d, such that $$D_n^{(d)} \le c(d) \frac{(\log n)^d}{n}$$ for all $n \gt 1$.

Generalized Faure sequences can be defined for any prime base $b \ge d$. The lowest bound for the discrepancy is obtained for the smallest prime $b \ge d$, so the base defaults to the smallest prime greater than or equal to the dimension.

The generalized Faure sequence $x_1, x_2, \ldots$, is computed as follows:

Write the positive integer n in its b-ary expansion, $$n=\sum_{i=0}^\infty a_i(n)b^i$$ where $a_i(n)$ are integers, $0 \le a_j(n) \lt b$.

The j-th coordinate of $x_n$ is $$x_n^{(j)} = \sum_{k=0}^\infty \sum_{d=0}^\infty c_{kd}^{(j)} a_d(n) b^{-k-1}, \,\, 1 \le j \le d$$

The generator matrix for the series, $c_{kd}^{(j)}$, is defined to be $$c_{kd}^{(j)} = j^{d-k} c_{kd}$$ and $c_{kd}$ is an element of the Pascal matrix, $$c_{kd} = \left\{ \begin{array}{ll} \frac{d!}{c! (d-c)!} & k \le d \\ 0 & k \gt d \end{array} \right.$$

It is faster to compute a shuffled Faure sequence than to compute the Faure sequence itself. It can be shown that this shuffling preserves the low-discrepancy property.

The shuffling used is the b-ary Gray code. The function G(n) maps the positive integer n into the integer given by its b-ary expansion. The sequence computed by this function is $\vec{x}(G(n))$, where $\vec{x}$ is the generalized Faure sequence.

See Also:

Example, Serialized Form

Constructor Summary

Constructors

Constructor and Description
FaureSequence(int dim) Creates a Faure sequence with the default base.
FaureSequence(int dim, int base, int nSkip) Creates a Faure sequence.

Method Summary

Modifier and Type	Method and Description
Object	clone() Returns a copy of this object.
int	getBase() Returns the base.
long	getCount()
int	getDimension() Returns the dimension of the sequence.
int	getSkip() Returns the number of points skipped at the beginning of the sequence.
double	nextDouble() Returns the first value of the next point in the sequence.
double[]	nextPoint() Returns the next point in the sequence.
static int	nextPrime(int n) Returns the smallest prime greater than or equal to n.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FaureSequence

public FaureSequence(int dim)

Creates a Faure sequence with the default base. The base defaults to the smallest prime equal to or greater than dim.

Parameters:

dim - is the dimension of the sequence.

FaureSequence

public FaureSequence(int dim,
                     int base,
                     int nSkip)

Creates a Faure sequence.

Parameters:

dim - is the dimension of the sequence.

base - is the base of the sequence, as described above. It must be at least as large as dim.

nSkip - is the number of initial points to skip. If negative then ${\it base}^{m/2-1}$, where m is the number of digits needed to represent the Integer.MAX_VALUE in the base, points are skipped.

Method Detail

clone

public Object clone()

Returns a copy of this object.

Overrides:

clone in class Object

getSkip

public int getSkip()

Returns the number of points skipped at the beginning of the sequence.

getDimension

public int getDimension()

Returns the dimension of the sequence.

Specified by:

getDimension in interface RandomSequence

getBase

public int getBase()

Returns the base.

getCount

public long getCount()

nextPoint

public double[] nextPoint()

Returns the next point in the sequence.

Specified by:

nextPoint in interface RandomSequence

Returns:

a double array, the next point in the sequence.

nextDouble

public double nextDouble()

Returns the first value of the next point in the sequence. This method is intended for use when dim is 1.

Returns:

a double array, the next sequence value.

nextPrime

public static int nextPrime(int n)

Returns the smallest prime greater than or equal to n.

Parameters:

n - is the first number to try as a prime.

Returns:

a prime greater than or equal to n. If n is less than or equal to 2 then 2 is returned.