User's Guide: Testing:Statistical Tests

Statistical Tests

The basic idea behind the statistical tests of randomness is that the random number streams obtained from a generator should have the properties of a sample drawn from a uniform distribution. Tests are designed so that the expected value of some test statistic is known for the uniform distribution. The empirically generated random number stream is then subjected to the same test, and the statistic obtained is compared against the expected value. While a boundless number of tests can be constructed, certain tests have become popular and are accepted as the de facto standard. Generators that pass such tests are considered "good". The series of tests proposed by Knuth and the DIEHARD tests implemented by Marsaglia are practically considered the standard tests.

These tests check a random number stream for the uniformity of the stream and for correlations between numbers in the stream. In a parallel random number generator, we include the additional restriction that there should not be correlations between different random number streams. For example, it should not so happen that most of the random numbers streams generate high random numbers in similar positions. If we interleave two streams such that the new stream generated has alternate numbers from the same stream, then this new stream should pass the tests for a serial random number stream if the original streams were not correlated. This testing scheme can be generalized to interleaving several streams to form a new stream.

Sequential Tests

These tests were proposed by Knuth and are widely used to check the quality of the random number streams.

We tested several streams from our our random number generators, producing a total of around 10¹¹ random numbers for each test given below. The test statistics obtained for all the streams were then subjected to the Kolmogorov-Smirnov test. The results were considered acceptable if they were not in the 1% tails. Our generators pass all these tests.

The tests performed included the following: Coupon collector's test, Equidistribution test, Gap test, Maximum of t test, Permutations test, Poker test, Runs test and Serial test.

Parallel Tests

We performed parallel versions of these tests in which we interleaved several streams at a time. We give details for the serial test below.

Serial Test

We also parallelized the set of tests described above in which we interleaved 256 streams to produce a new stream. In the preliminary tests, we generated a total of 10⁸ random numbers in each test. We also performed the runs test and the gap test in which we tested 4 sets of 256 streams each for a total of 1024 streams, generating about 10¹² random numbers in the process. Both our generators passed these parallel tests.

Sum of distributions test:

We can use the fact that the sum of independent variables approaches the normal distribution to test for the independence of random number streams. We add random numbers from several streams and form a sum. We generate several such sums and check if their distribution is normal. In our tests, we formed sums by adding 128 random numbers each from 1024 streams. We checked the distribution of 10⁶ sums for a total of around 10¹¹ random numbers. Our generators performed acceptably.

DIEHARD Tests

The DIEHARD tests were proposed and implemented by Marsaglia, and are considered to be more stringent tests of randomness than the tests proposed by Knuth. The DIEHARD code is not easy to modify, and so we have not modified any of the parameters used in these tests. The results of this test indicate that the SPRNG generators perform acceptably.