Interval (gap) test


The interval test is a particular version of the gap test. The basic idea is to look at the intervals between successive occurrences of the same value. For instance, suppose that random() produces the value 3. Determine the number of values that random() produces up to and including the next occurrence of 3. Repeat this for all successive appearances of the value 3 in the output sequence. Count the number of separations of length 1, 2, 3, etc. Compute a chi-square statistic using these counts and the expected counts for each separation length, 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.

As stated, the interval test is impractical, since with 2**31 possible output values and a period much longer than that, the separation between successive values will usually be enormous, and practicality limits the number of values we can use in this or any other test. Instead of using the entire value produced by random(), we limit ourselves to look at the values of only small fields (no more than 4 bits). Even so, some separations might be quite large. We simply ignore any separation over a certain size, set to insure that the smallest expected count for any separation size is at least 64, given the number of random variables used in each test (32,768).

We avoided the issue of which value(s) to use by simply using the first value in the sequence for each test. Since the number of possible values is quite small (no more than 16), each value is likely to be used many times, and no single value is favored.

Return to the testing home page.