TAOCP Vol 2: Seminumerical Algorithms · Week 56
TAOCP 3.5 What Is a Random Sequence?: reading guide
A philosophical and mathematical attempt to define randomness for infinite and finite sequences, building up through stronger and stronger definitions and touching on what later became algorithmic (Kolmogorov) complexity.
Time About 6 hours this week
Why it matters
Mostly for intellectual depth, but it sharpens your intuition about why "passes some tests" can never fully define random, and connects to compression and cryptography.
Before you start
- 3.3 Statistical Tests
How to approach it
Read for ideas. Follow the sequence of definitions and why each one is too weak. The heavy proofs can be skimmed on a first pass.
Exercises
The exercises here lean heavily on M and HM ratings. Try a couple of the lower ones; skip the rest without guilt.
Traps
- Expecting a practical takeaway on every page. This one is about understanding.