Diehard tests
The diehard tests are a battery of statistical tests for measuring the quality of a random number generator (RNG).
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The diehard tests are a battery of statistical tests for measuring the quality of a random number generator (RNG). They were developed by George Marsaglia over several years and first published in 19951 on a CD-ROM of random numbers. In 2006, the original diehard tests were extended into the dieharder tests.
Choose m birthdays in a year of n days. List the spacings between the birthdays. If is the number of values that occur more than once in that list, then is asymptotically Poisson-distributed with mean .
Experience shows n must be quite large, say n ≥ 2 , for comparing the results to the Poisson distribution with that mean. This test uses n = 2 and m = 2 , so that the underlying distribution for is taken to be Poisson with . A sample of 500 s is taken, and a chi-square goodness of fit test provides a p value.
The first test uses bits 1–24 (counting from the left) from integers in the specified file. Then the file is closed and reopened. Next, bits 2–25 are used to provide birthdays, then 3–26 and so on to bits 9–32.
Each set of bits provides a p-value, and the nine p-values provide a sample for a KSTEST. In a square of side 100, randomly "park" a car – a circle of radius 1. Then try to park a 2nd, a 3rd, and so on, each time parking "by ear".
That is, if an attempt to park a car causes a crash with one already parked, try again at a new random location. (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.
If we plot n: the number of attempts, versus k the number successfully parked, we get a curve that should be similar to those provided by a perfect random number generator. 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. Thus should be a standard normal variable, which, converted to a uniform variable, provides input to a KSTEST based on a sample of 10. It does this 100 times choose n = 8000 random points in a square of side 10000.
Find d, the minimum distance between the pairs of points. If the points are truly independent uniform, then , the square of the minimum distance should be (very close to) exponentially distributed with mean 0.995. Thus should be uniform on [0,1) and a KSTEST on the resulting 100 values serves as a test of uniformity for random points in the square.
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. Random integers are floated to get uniforms on [0,1).
Starting with k = 2 = 2147483648, the test finds , the number of iterations necessary to reduce k to 1, using the reduction k = ceiling(k×U), with U provided by floating integers from the file being tested. Such s are found 100000 times, then counts for the number of times was are used to provide a chi-square test for cell frequencies.
Integers are floated to get a sequence U(1), U(2), ... of uniform [0,1) variables. Then overlapping sums, S(1) = U(1) + ... + U(100), S(2) = U(2) + ... + U(101), ... are formed. The Ss are virtually normal with a certain covariance matrix.
A linear transformation of the Ss converts them to a sequence of independent standard normals, which are converted to uniform variables for a KSTEST. The p-values from ten KSTESTs are given still another KSTEST. OQSO means overlapping-quadruples-sparse-occupancy.
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. The mean number of missing words in a sequence of 2 four-letter words, (2 + 3 "keystrokes"), is again 141909, with sigma = 295.
The mean is based on theory; sigma comes from extensive simulation. The DNA test considers an alphabet of 4 letters C, G, A, T, determined by two designated bits in the sequence of random integers being tested.
It considers 10-letter words, so that as in OPSO and OQSO, there are 2 possible words, and the mean number of missing words from a string of 2 (overlapping) 10-letter words (2 + 9 "keystrokes") is 141909. The standard deviation, sigma = 339, was determined as for OQSO by simulation. The standard deviation for OPSO is 290 to three places, and was determined without simulation.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373154256 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Diehard tests” publication date (×1) · confidence 0.95 revision URL