Testing random number generators
Random number generators are subtle. Unless the generator is some physical device, random number generators (RNGs) are usually technically pseudorandom number generators (PRNGs), deterministic algorithms designed to mimic randomness.
Suppose you have a PRNG that produces the digits 0 through 9. How might you test the output to see whether it (acts like it) is random? An obvious test would be to see how often each digit is produced. As the number of samples n increases, you'd expect the frequency of each digit to approach n/10.
Starting with ^2If your random" number generator simply cycles through the digits 0 to 9 in order, the frequencies will match expectations. In fact, they will match too well. A two-sided ^2 test will catch this problem. The ^2 will be too small, indicating a suspiciously even distribution.
Nick Lord [1] gives a construction that has a much more subtle pattern. In his example, the frequencies also converge to the expect values, but the ^2 statistic diverges to as n increases. So rather than producing too small a ^2 value, his example produces too large a value. This shows that the ^2 test is a stronger test than simply looking at frequencies, but it's only a start.
RNG testing serviceThere are more sophisticated tests, and standard suites of tests: DIEHARDER, NIST STS, TestU01, etc. We've run these test suites for several clients. More on that here.
It's curious how this work comes in spurts. We had a run of clients wanting RNG testing, then nothing for a long time, and now we have a new RNG testing project in the queue.
Related posts[1] A Chi-Square Nightmare. The Mathematical Gazette, Vol. 76, No. 476 (July 1992), p. 274.
The post Testing random number generators first appeared on John D. Cook.