Package 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:

  • Constructor Summary

    Constructors
    Constructor
    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
    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 Details

    • 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 Details

    • 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.