next up previous
Next: Spectral Test Up: Statistical Tests Previous: Lag- Autocorrelation

Coupon Collector's Test

In this test, we examine a sequence of random numbers and record the lengths of successive ``complete sets'' of integers from $0$ to $d-1$. In our implementation, it was not feasible to use $d > 3$ (this is because the Stirling Numbers of Second Kind get very large and produce overflow errors), so we examined complete sets of $\{0,1,2\}$. At the conclusion of the algorithm, COUNT[r] represents the number of segments with with length r, for $d \le r < t$, and COUNT[t] is the number of segments with length $\ge t$. For our experiments, we used $t=20$.

The next step is to compare the frequencies of occurrence with the expected frequencies. The expected probabilities are as follows.


\begin{displaymath}
p_r = \frac{d!}{d^r}
\left\{
\begin{array}{c}
r-1\\
d-1\\
\end{array}\right\} for \; d \le r < t
\end{displaymath}


\begin{displaymath}
p_t = 1-\frac{d!}{d^{t-1}}
\left\{
\begin{array}{c}
t-1\\
d\\
\end{array}\right\}
\end{displaymath}

Here $\left\{
\begin{array}{c}
a\\
b\\
\end{array}\right\}$ represents the Stirling's Number of Second Kind with parameters $a$ and $b$.

We apply the $\chi ^2$ test to COUNT[d], COUNT[d+1],..., COUNT[t] with the degree of freedom, $k=t-d+1$.



2001-05-30