The coupon collectors test examines the random number generator output for covers; i.e., subsequences which contain at least one of each category of values and which do not contain covers as proper subsequences themselves.
Having every possible value that the random number generator can produce be in a category by itself is impractical (and not particularly interesting, because of the periodic structure of the output sequence). Instead, the coupon collectors test assigns many values to each of a small number of groups. One of the simplest methods, and the one used here, is to use short fields of adjacent bits from the random numbers to identify the group.
The test generates random numbers and uses the selected bits as an group index. Each group gets checked off when a random number indexes that group. The shortest subsequence which indexes all groups is called a cover. The length of a cover is random, and the distribution of cover lengths can be predicted from the assumption of uniform random numbers.
Obviously, covers are at least as long as the number of groups, and can be arbitrarily long. The coupon collectors test used here arbitrarily counts only the first 10 possible cover sizes. All covers longer than these are counted in a separate group, for a total of 11 groups and 10 degrees of freedom.
The number of covers for each group must be at least equal to a specified minimum (100 here). In order to have the minimum number of covers in each group, some groups may have an expected number of covers that is very large. For this reason, the test is limited to using 1-, 2-, and 3-bit fields. Also, the number of random numbers which must be generated to produce enough covers is itself a random number that depends in part on the probability that a cover begins at specific positions in the generator's output sequence. This probability changes as the index of the position grows, but it eventually will converge to a "steady-state" value. Our tests skip over the first few outputs of the generator and start looking for covers only when the cover start probability has converged to within 10**(-10) of its asymptotic value.
Return to the testing home page.