5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Have you seen Diehard? $\endgroup$ – J. M. is not a statistician Sep 14 '11 at 16:26
  • 1
    $\begingroup$ If I recall correctly, Volume 2 of the Art of Computer Programming has a lot on this subject, though it may be out of date. $\endgroup$ – David Speyer Sep 14 '11 at 17:14
  • $\begingroup$ My understanding is that Dieharder and TestU01 are suites of tests to see whether an RNG is reasonable as a stand-in for a uniformly distributed source. If one is starting from data that's supposed to be normal, maybe it would make sense to apply a transformation that would take normally distributed data and generate uniformly distributed data, and then apply one of the test suites? $\endgroup$ – Mars May 12 '19 at 3:33
  • $\begingroup$ There are books by Kneusel and Johnston that are very recent and include a lot of information that was unavailable at the time of the 3rd ed of TAOCP chapter 3, volume 2, but much of TAOCP is still relevant, and there is depth to the explanations in TAOCP that's unsurprisingly lacking in parts of the recent books. I've found all three useful. $\endgroup$ – Mars May 12 '19 at 3:41
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ TestU01 is also worth considering. $\endgroup$ – Mars May 12 '19 at 3:29
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.