How can I test the quality of a RNG?

Question

On electronics.stackexchange we had a question about constructing a True Random Number Generator. Since the method relies on noise, which isn't deterministic, the only way to test the quality of the RNG seems to be empirical.
Not being a statistician I suggested to test a long bit sequence for normality, but I have no idea what outcome is acceptable and what isn't. For instance counting single bits I guess we have a thumbs-up for a 499500/500500 distribution, but when is the ratio too much skewed to be acceptable? Same for 2-bit and longer sequences.
Of course, if testing for normality is a Bad Idea™, I'd like to hear it, including better alternatives.

edit
Diehard was mentioned a few times, but I'm not sure this answers my question. The normality test should give a normal distribution, with better bell curve approximations for longer sequences. Diehard seems also to have tests which either should result in normal or exponential distributions. But my question remains: how do I judge the results? Just by looking at the curve and discern a bell curve in it? To get back at my first example, a 499500/500500 distribution is definitely OK, and a 950000/50000 distribution definitely is a no-no, so where does the switch-over happen?

Answer 1

J.M. already mentioned the original Diehard battery of tests by George Marsaglia. As far as I know, this test set is no longer being maintained.

Robert Brown has been working for years on DieHarder which is

• a GPL'ed reimplementation of the DieHard suite
• plus additional tests from the NIST suite
• plus development of new tests

and you may find DieHarder useful.

Answer 2

You're right: testing is empirical. It's all done in a standard hypothesis testing framework. Different tests are applied to assess different alternative behaviors of RNGs. As always, the user is free to choose the level of confidence with which each test is conducted. This level determines the critical region of each test, which is the "switch over" between a "significant" result and one not considered significant.

In practice, the confidence level matters little, because most RNGs can generate such a long series of values that eventually any long-run departure from complete, independent, equidistributed randomness will be detectable with high confidence. (This is the main reason that proper application of test suites like DieHard require you to generate a large number of bits at a minimum. I recollect--it has been a while--that early versions demanded 80 million bits.) Typically, an RNG will pass many tests thrown at it (otherwise it would never have seen the light of day) but it will clearly blow a few of them.