What RNG tests can and cannot prove

Chi-square, Diehard, the NIST suite, TestU01 — the statistical batteries that certify random number generators, and the limits their own authors spell out: about 1% of sequences from a perfect generator fail any given test by design, no finite battery is ever complete, and NIST states plainly that testing is not a substitute for cryptanalysis.

A random number generator that has “passed its tests” sounds settled. It is worth understanding exactly what that sentence claims — and what the people who wrote the tests say it cannot. Statistical testing is powerful and necessary. It is also, by its own authors’ account, a filter that catches specific flaws rather than a proof of randomness. This chapter lays out the batteries, then the limits, in the standards’ own words.

The batteries

Gaming certification does not prescribe one fixed battery. GLI-11 delegates the choice to the laboratory “on a case-by-case basis” and lists a menu of statistical tests it “may include”: a Total Distribution or Chi-square test, an Overlaps test, a Coupon Collector’s test, a Runs test, Interplay Correlation and Serial Correlation tests, and a Duplicates test. Each targets a particular way a sequence could betray structure — a skew in how often each value appears, a dependency between successive draws, an unlikely spacing of repeats.

Beyond gaming, three general-purpose batteries dominate. Diehard (George Marsaglia, 1995) was the original well-known collection. NIST SP 800-22 is the cryptographic-application suite — “a statistical package consisting of 15 tests” including the Frequency (Monobit), Runs, Binary Matrix Rank, Discrete Fourier Transform (Spectral), Linear Complexity and Approximate Entropy tests. And TestU01 (L’Ecuyer & Simard, 2007) is the modern, most demanding library, an open-source C package whose batteries SmallCrush, Crush and BigCrush run tens or hundreds of tests each. These are free and public; the interpretive layer around them is where the honesty has to live.

What one test actually does

A statistical test states a null hypothesis — “this sequence is random” — and computes a p-value, the probability of seeing data at least this extreme if the null were true. You then pick a significance level, α. NIST’s rule is the standard one: “If P-value ≥ α, then the null hypothesis is accepted… If P-value < α, then the null hypothesis is rejected”. The suite suggests choosing α “in the range [0.001, 0.01].” A test never proves randomness; it only fails to find the one pattern it was built to detect.

The 1% that fails by design

Here is the fact that reframes every “it failed a test” headline. Because failure is defined by a threshold on a probability, a perfect generator is expected to fail some of the time. NIST spells out the arithmetic: “An α of 0.01 indicates that one would expect 1 sequence in 100 sequences to be rejected”. Run a hundred sequences from a flawless source through one test at α = 0.01 and roughly one will “fail” — not because the source is broken, but because that is what a 1% false-alarm rate means. This is why a lone failure triggers investigation and re-testing rather than condemnation, and why GLI-11 requires the chosen tests to be “evaluated, collectively, at a 99% confidence level” rather than trusting any single result.

No battery is ever complete

You cannot fix the gap by adding more tests until you have “all” of them. NIST states the principle directly: “Because there are so many tests for judging whether a sequence is random or not, no specific finite set of tests is deemed ‘complete.’” A generator can sail through one battery and be exposed by a sharper one. The canonical example is the Mersenne Twister, for decades the default generator in much scientific software: it passes a great deal, yet the linear-complexity test in TestU01’s Crush and BigCrush batteries detects its non-random structure — “can actually find nonrandom behavior in the Mersenne Twister… in less than five seconds, using fewer than 75,000 generated numbers”. The reason is structural: the Mersenne Twister is built on a linear recurrence, and a test aimed at linear structure eventually sees through it. “Passed the tests” always means these tests, on this data.

The limit, in NIST’s own words

The strongest statement of the boundary is the one NIST puts in its abstract, and it is worth quoting in full: “no set of statistical tests can absolutely certify a generator as appropriate for usage in a particular application, i.e., statistical testing cannot serve as a substitute for cryptanalysis”. Statistical tests examine output for the absence of detectable patterns. Whether a generator is unpredictable — whether an adversary who studies its design can forecast it — is a question about the algorithm, answered by cryptanalysis, which the standard says is “outside the scope of this paper.” The weak generator in the previous chapter can produce output that looks fine to a quick test right up until six samples let you predict it exactly.

So what does a pass mean?

It means something real and worth having: the generator’s output showed no evidence of the specific weaknesses the chosen tests probe, at the confidence level set, on the volume of data collected. That rules out a large class of broken generators, which is exactly why testing is mandatory. What it does not do is prove randomness, prove unpredictability, or promise that a more demanding test — or an attacker who reads the source code — would not find something. Read “passed its statistical tests” as a cleared bar, not a closed case. What a laboratory certificate does and does not assert on top of these tests is the next chapter.

Common questions

Sources (4)

• NIST SP 800-22 Rev. 1a — A Statistical Test Suite for Random and Pseudorandom Number Generators (abstract, §1.1.5, §2)nvlpubs.nist.gov
• GLI-11 Gaming Devices in Casinos, v3.0 (2016) — §3.2.2 Statistical Analysis (RNG test menu, 99% confidence)gaminglabs.com
• TestU01 (L’Ecuyer & Simard, ACM TOMS 2007) — open-source empirical RNG test library (SmallCrush / Crush / BigCrush)github.com
• M. E. O’Neill, PCG paper — the linear-complexity test detects non-randomness in the Mersenne Twister (citing L’Ecuyer & Simard 2007)pcg-random.org

Education, not advice. This chapter explains how the random number generators behind casino games are built, tested and certified so you can judge the claims made about them honestly. It is not a system, and nothing here treats gambling as a way to make money — over enough play the mathematics favours the house. 18+.