Tests for Randomness

Many tests for randomness have been proposed over time. Sadly, most of these tests are statistical in nature, and tend to concentrate on measuring bias. Still, statistical tests are better than no tests.

The basic principle is to pick an understood property and see if the generator has it. For example; if we toss a coin 3 times, we'd expect to flip three heads about 1 time in 8. Take the output of the generator in groups of three and use that to toss three virtual coins 8,000,000 times. Now count the number of sets of three heads. We can calculate the probability of that many sets occuring if the generator is unbiased. If it's less than, say, 1/1000 we call it a failure and question the generator more closely.

Note that a failure rate of 1/1000 means we should expect a good generator to "fail" if we test it 1000 times. Indeed, failing to fail is itself a failure. Although generators can fail at random, bad generators generally fail spectacularly. The Only OK generator will pass most of the diehard tests, but a few of it's results have a less than .000000001 chance of occuring in an unbiased generator.

Also keep in mind that most tests test only for failure. Failing is bad, but passing means little.