Testing random variate generation algorithms

Question

Which methods are used for testing random variate generation algorithms?

Answer 1

The Diehard Test Suite is something close to a Golden Standard for testing random number generators. It includes a number of tests where a good random number generator should produce result distributed according to some know distribution against which the outcome using the tested generator can then be compared.

EDIT

I have to update this since I was not exactly right: Diehard might still be used a lot, but it is no longer maintained and not state-of-the-art anymore. NIST has come up with a set of improved tests since.

Answer 2

Just to add a bit to honk's answer, the Diehard Test Suite (developed by George Marsaglia) are the standard tests for PRNG.

There's a nice Diehard C library that gives you access to these tests. As well as the standard Diehard tests it also provides functions for a few other PRNG tests involving (amongst other things) checking bit order. There is also a facilty for testing the speed of the RNG and writing your own tests.

There is a R interface to the Dieharder library, called RDieHarder:

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

This shows that the RANDU RNG generator fails the minimum-distance / 2dsphere test.

Answer 3

For testing the numbers produced by random number generators the Diehard tests are a practical approach. But those tests seem kind of arbitrary and one is may be left wondering if more should be included or if there is any way to really check the randomness.

The best candidate for a definition of a random sequence seems to be the Martin-Löf randomness. The main idea for this kind of randomness, is beautifully developed in Knuth, section 3.5, is to test for uniformity for all types of sub-sequences of the sequence of random numbers. Getting that all type of subsequences definition right turned out to be be really hard even when one uses notions of computability.

The Diehard tests are just some of the possible subsequences one may consider and their failure would exclude Martin-Löf randomness.

Answer 4

You cannot prove, because it is impossible; you can only check if there are no any embarrassing autocorrelations or distribution disturbances, and indeed Diehard is a standard for it. This is for statistics/physics, cryptographers will also mainly check (among other things) how hard is it to fit the generator to the data to obtain the future values.

Answer 5

Small correction to Colin's post: the CRAN package RDieHarder is an interface to DieHarder, the Diehard rewrite / extension / overhaul done by Robert G. Brown (who kindly lists me as a coauthor based on my RDieHarder wrappers) with recent contribution by David Bauer.

Among other things, DieHarder includes the NIST battery of tests mentioned in Mark's post as well as some new ones. This is ongoing research and has been for a while. I gave a talk at useR! 2007 about RDieHarder which you can get from here.

Answer 6

There are two parts to testing a random number generator. If you're only concerned with testing a uniform generator, then yes, something like the DIEHARD test suite is a good idea.

But often you need to test a transformation of a uniform generator. For example, you might use a uniform generator to create exponentially or normally distributed values. You may have a high-quality uniform generator -- say you have a trusted implementation of a well-known algorithm such as Mersenne Twister -- but you need to test whether the transformed output has the right distribution. In that case you need to do some sort of goodness of fit test such as Kolmogorov-Smirnov. But for starters, you could verify that the sample mean and variance have the values you expect.

Most people don't -- and shouldn't -- write their own uniform random number generator from scratch. It's hard to write a good generator and easy to fool yourself into thinking you've written a good one when you haven't. For example, Donald Knuth tells the story in TAOCP volume 2 of a random number generator he wrote that turned out to be awful. But it's common for people to have to write their own code to produce random values from a new distribution.

Answer 7

It's seldom useful to conclude that something is "random" in the abstract. More often you want to test whether it has a certain kind of random structure. For example, you might want to test whether something has a uniform distribution, with all values in a certain range equally likely. Or you might want to test whether something has a normal distribution, etc. To test whether data has a particular distribution, you can use a goodness of fit test such as the chi square test or the Kolmogorov-Smirnov test.

Answer 8

The NIST publishes a list of statistical tests with a reference implementation in C.

There is also TestU01 by some smart folks, including respected PRNG researcher Pierre L'Ecuyer. Again, there is a reference implementation in C.

As pointed out by other commenters, these are for testing the generation of pseudo random bits. If you transform these bits into a different random variable (e.g. Box-Muller transform from uniform to Normal), you'll need additional tests to confirm the correctness of the transform algorithm.