IMSL C# Numerical Library

FaureSequence Class

Generates the low-discrepancy Faure sequence.

For a list of all members of this type, see FaureSequence Members.

System.Object
   Imsl.Stat.FaureSequence

public class FaureSequence : IRandomSequence

Thread Safety

Public static (Shared in Visual Basic) members of this type are safe for multithreaded operations. Instance members are not guaranteed to be thread-safe.

Remarks

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.

Requirements

Namespace: Imsl.Stat

Assembly: ImslCS (in ImslCS.dll)

See Also

FaureSequence Members | Imsl.Stat Namespace | Example