:: Online Library of Programming Tutorials and Courses ::
    Return to :: The Online Library
next up previous
Next: Frequency test Up: Random-Number Generation Previous: Combined Linear Congruential Generators

Tests for Random Numbers

When a random number generator is devised, one needs to test its property. The two properties we are concerned most are uniformity and independence. A list of tests will be discussed. The first one tests for uniformity and the second to fifth ones test independence.

  1. Frequency test
  2. Runs test
  3. Autocorrelation test
  4. Gap test
  5. Poker test

The algorithms of testing a random number generator are based on some statistics theory, i.e. testing the hypotheses. The basic ideas are the following, using testing of uniformity as an example.

We have two hypotheses, one says the random number generator is indeed uniformly distributed. We call this tex2html_wrap_inline2159 , known in statistics as null hypothesis. The other hypothesis says the random number generator is not uniformly distributed. We call this tex2html_wrap_inline2161 , known in statistics as alternative hypothesis.

We are interested in testing result of tex2html_wrap_inline2159 , reject it, or fail to reject it.

To see why we don't say accept H null, let's ask this question: what does it mean if we had said accepting H null? That would have meant the distribution is truely uniform. But this is impossible to state, without exhaustive test of a real random generator with infinite number of cases. So we can only say failure to reject H null, which means no evidence of non-uniformity has been detected on the basis of the test. This can be described by the saying ``so far so good''.

On the other hand, if we have found evidence that the random number generator is not uniform, we can simply say reject H null.

It is always possible that the tex2html_wrap_inline2159 is true, but we rejected it because a sample landed in the tex2html_wrap_inline2161 region, leading us to reject tex2html_wrap_inline2159 . This is known as Type I error. Similarily if tex2html_wrap_inline2159 is false, but we didn't reject it, this also results in an error, known as Type II error.

With these information, how do we state the result of a test? (How to perform the test will be the subject of next a few sections)

  • A level of statistical significance tex2html_wrap_inline1935 has to be given. The level tex2html_wrap_inline1935 is the probability of rejecting the H null while the H null is true (thus, Type I error).

    displaymath2157

  • We want the probability as little as possible. Typical values are 0.01 (one percent) or 0.05 (five percent).
  • Decreasing the probability of Type I error will increase the probability of Type II error. We should try to strike a balance.

For a given set of random numbers produced by a random number generator, the more tests are, the more accurate the results will be.




next up previous
Next: Frequency test Up: Random-Number Generation Previous: Combined Linear Congruential Generators

Xiannong Meng
Wed Aug 12 15:44:51 CDT 1998