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

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

contained in E.

The sequence $x_1, x_2, \ldots$ of points in 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

are integers, $0 \le a_j(n) \lt b$ .

The j-th coordinate of 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)

FaureSequence Class

Thread Safety

Remarks

Requirements

See Also