Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 38 · Random Numbers

Testing Randomness

Check a random number generator with a chi-square uniformity test, a runs test and autocorrelation, and learn what a p-value does and does not tell you.

How do you know a stream of numbers is "random enough"? You cannot prove randomness, but you can test for specific kinds of non-randomness. If a generator passes many independent tests, you gain confidence; if it fails one, you have found a flaw. This lesson builds three basic tests and explains how to read their results.

The idea of a statistical test

A statistical test starts from a null hypothesis: here, "these numbers are independent and uniform on [0, 1)". It computes a test statistic from the data and asks: if the null hypothesis were true, how likely is a statistic at least this extreme? That probability is the p-value.

  • A large p-value (say 0.3) means the data look ordinary under the null hypothesis.
  • A very small p-value (say 0.0001) is suspicious.

Two cautions. First, a good generator will produce a p-value below 0.05 about 5% of the time by pure chance, so one small p-value is not proof of a bad generator; repeat the test. Second, a large p-value does not prove randomness; it only means this test found nothing.

Test 1: uniformity with chi-square

Split [0, 1) into k equal bins. With n uniform numbers, each bin should receive about n/k. The chi-square statistic measures the total discrepancy:

Text
χ² = Σ (observed − expected)² / expected

Under the null hypothesis, χ² follows a chi-square distribution with k − 1 degrees of freedom.

Python Chi-square test for uniformity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The squeezed data leave the outer bins empty, so χ² is huge and the p-value is essentially zero. Notice what this test cannot see: it ignores order, so the numbers 0.00, 0.01, 0.02, … sorted in ascending order would pass it perfectly.

Test 2: independence with a runs test

A run is a maximal stretch of consecutive values that stay on one side of the median (or keep going up, or going down). Truly independent data change direction at a predictable rate. Too few runs means numbers cluster (long stretches high, then low); too many means they alternate suspiciously.

For n₁ values above the median and n₂ below, the expected number of runs and its variance are

Text
mean = 2·n₁·n₂/(n₁+n₂) + 1
var  = (mean − 1)(mean − 2)/(n₁+n₂ − 1)

and the standardized count is approximately normal.

Python Wald–Wolfowitz runs test

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed tuple is (runs, expected runs, z, p). The sticky sequence has far fewer runs than expected, so z is a large negative number and p is tiny, even though its values still cover a range.

Test 3: autocorrelation

The autocorrelation at lag h is the correlation between the sequence and itself shifted by h steps. For independent numbers it should be near 0 at every lag, with typical size 1/√n. An approximate 95% band is ±1.96/√n.

Python Autocorrelation at several lags

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 30 lags and a 5% error rate per lag, one or two bars poking outside the red band is normal. A pattern (many bars outside, or a bar at lag 1 far outside) is the warning sign.

Test batteries

Real generators are judged by large collections of such tests:

  • Diehard / Dieharder, an older battery of statistical tests.
  • TestU01 (SmallCrush, Crush, BigCrush), the standard for serious assessment.
  • PractRand, which keeps testing bigger and bigger samples until a failure appears.

The default generator in NumPy (PCG64) and Python's Mersenne Twister are widely checked. You rarely need to test them yourself, but running small tests like those above on your own constructions (like the LCG from the last lesson) teaches you what failure looks like.

Test the thing you actually use. If your simulation relies on pairs of consecutive numbers, test pairs; if it relies on the low bits, test the low bits.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does a p-value of 0.0001 in a chi-square uniformity test suggest?

    A tiny p-value means the observed discrepancy would be very rare if the numbers were uniform, which casts doubt on the generator.
  2. 2. A sorted list 0.00, 0.01, ..., 0.99 passes the chi-square uniformity test. What does this show?

    The test counts values per bin and ignores order, so ordered data can pass; independence tests are needed as well.
  3. 3. For 10,000 independent uniform numbers, roughly what band should autocorrelations at each lag fall in?

    The band is about ±1.96/√n = ±1.96/100 ≈ ±0.02.
  4. 4. A good generator is tested 100 times at the 5% level. About how many 'failures' do you expect by chance?

    At the 5% level a true null is rejected about 5% of the time, so about 5 out of 100.

Summary

  • A statistical test measures how surprising the data would be under "independent and uniform"; the p-value is that probability.
  • Chi-square tests uniformity but ignores order; runs and autocorrelation tests look at independence.
  • A single small p-value can be chance; repeated or extreme failures mean a real flaw.
  • Passing tests does not prove randomness; it only means these tests found nothing.
  • Professional batteries (TestU01, PractRand) test generators far more deeply.

Next: NumPy Generators and Reproducibility