TAOCP Vol 2: Seminumerical Algorithms · Week 50
TAOCP 3.3.1 General Test Procedures: reading guide
The statistical machinery for testing a generator: the chi-square test for counts in categories, and the Kolmogorov-Smirnov test for continuous distributions, plus how to read their results without fooling yourself.
Time About 7 hours this week
Why it matters
These tests are how you check any claim of "uniform" or "random", whether it is a PRNG, a load balancer, or an A/B test bucketing scheme.
Before you start
- Basic probability and statistics
- 3.2 Generating Uniform Random Numbers
How to approach it
Implement chi-square on dice rolls from a good and a bad generator. Implement KS on uniform floats. Run each test many times and see that even a perfect generator "fails" sometimes; that is the point of p-values.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Treating one failed test as proof of a bad generator, or one pass as proof of a good one.