They were developed by George Marsaglia over several years and first published in 1995 on a CD-ROM of random numbers.
[2] Most of the tests in DIEHARD return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits.
Those p-values are obtained by p = F(X), where F is the assumed distribution of the sample random variable X – often normal.
The inability to modify the test parameters or add new tests led to the development of the TestU01 library, introduced in 2007 by Pierre L’Ecuyer and Richard Simard of the Université de Montréal.
If j is the number of values that occur more than once in that list, then j is asymptotically Poisson-distributed with mean m3 / (4n).
Experience shows n must be quite large, say n ≥ 218, for comparing the results to the Poisson distribution with that mean.
A sample of 500 js is taken, and a chi-square goodness of fit test provides a p value.
Then the quadratic form in the weak inverse of the 120×120 covariance matrix yields a test equivalent to the likelihood ratio test that the 120 cell counts came from the specified (asymptotically) normal distribution with the specified 120×120 covariance matrix (with rank 99).
This test may have unresolved bugs resulting in consistently poor p-values.
The leftmost 31 bits of 31 random integers from the test sequence are used to form a 31×31 binary matrix over the field {0,1}.
Consider the file under test as a stream of bytes (four per 32-bit integer).
Now let the specified bytes from successive integers provide a string of (overlapping) 5-letter words, each "letter" taking values A, B, C, D, E. The letters are determined by the number of 1s, in that byte 0, 1, or 2 → A, 3 → B, 4 → C, 5 → D, and 6, 7 or 8 → E. Thus we have a monkey at a typewriter hitting five keys with various probabilities 37, 56, 70, 56, 37 over 256.
After 12,000 tries, the number of successfully parked circles should follow a certain normal distribution.
In a square of side 100, randomly "park" a car – a circle of radius 1.
(To avoid path problems, consider parking helicopters rather than cars.)
Each attempt leads to either a crash or a success, the latter followed by an increment to the list of cars already parked.
Theory for the behavior of such a random curve seems beyond reach, and as graphics displays are not available for this battery of tests, a simple characterization of the random experiment is used: k, the number of cars successfully parked after n = 12000 attempts.
Simulation shows that k should average 3523 with sigma 21.9 and is very close to normally distributed.
Randomly place 8000 points in a 10000×10000 square, then find the minimum distance between the pairs.
If the points are truly independent uniform, then d2, the square of the minimum distance should be (very close to) exponentially distributed with mean 0.995.
Test numbers = 0 mod 5 are printed but the KSTEST is based on the full set of 100 random choices of 8000 points in the 10000×10000 square.
Then the volume of the smallest such sphere is (very close to) exponentially distributed with mean 120π / 3.
Each min radius cubed leads to a uniform variable by means of 1 − exp(−r3 / 30), then a KSTEST is done on the 20 p-values.
Throws necessary to complete the game can vary from 1 to infinity, but counts for all > 21 are lumped with 21.
Consider an alphabet with two "letters", 0 and 1, and think of the stream of bits as a succession of 20-letter "words", overlapping.
For a truly random string of 221 + 19 bits, the number of missing words j should be (very close to) normally distributed with mean 141,909 and sigma 428.
Thus (j−141909) / 428 should be a standard normal variate (z score) that leads to a uniform [0,1) p value.
Each letter is determined by a specified ten bits from a 32-bit integer in the sequence to be tested.
The test OQSO is similar, except that it considers 4-letter words from an alphabet of 32 letters, each letter determined by a designated string of 5 consecutive bits from the test file, elements of which are assumed 32-bit random integers.
(Sigma for OPSO, 290, is the true value (to three places), not determined by simulation.