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.

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

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

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