Divide up the sequence produced by random() into non-overlapping subsequences of a fixed (small) length N. For each subsequence, we assume that the values in the subsequence are unique. Replace each value by its ranking based on magnitude. For instance, replace the smallest value by 1, the next smallest by 2, etc. The largest value is replaced by N. Each subsequence now becomes a permutation of the integers 1 to N.
Count how often each permutation occurs. Compute a chi-square statistic using these counts and the expected counts for each permutation (all permutations should occur with equal frequency), and compare its value with the critical value of a chi-square random variable of the appropriate number of degrees of freedom and a probability of 0.95.
Because of the large number of possible permutations even for modest values of N, N must be kept small - we limited N to no more than 7. Also, since there must be enough unique values to fill out each subsequence, the length of the subsequence constrains the minimum number of bits which can be used. For example, if we use length 5 subsequences, the number of bits must be enough to represent more than 5 distinct values, and hence we need to use at least 3-bit fields with length 5 subsequences.
Although we could have combined permutations into groups and counted the number of subsequences in each group, we chose not to do so, but to count each permutation separately. The number of permutations grows as N!, limiting the subsequence lengths we could use, since for reliable results, the chi-square test should be used with a minimum of five for each permutation count, and preferably much more than five.
Finally, since the test typically used only small bit fields, it was frequently the case that a value would be repeated within the same subsequence, making it impossible to describe each subsequence by a unique permutation. The solution to this problem was simply to throw away repeated values before the end of the subsequence was reached.
Return to the testing home page.