Connections in Math: the two kinds of random
5 hours ago
- #Algorithmic Information Theory
- #Kolmogorov Complexity
- #Shannon Entropy
- The puzzle contrasts two statistically identical files of a million digits: one is random noise; the other is the first million digits of π.
- Both files have uniform digit frequencies, making them indistinguishable by statistical tests and giving them maximal Shannon entropy—meaning no statistical redundancy for compression.
- However, π can be compressed significantly via a short program that computes it, while the random file cannot be compressed as it lacks a simple generating rule.
- Shannon entropy measures compressibility based on symbol frequencies in a source, while Kolmogorov complexity measures the length of the shortest program that outputs a specific string, capturing structural compressibility.
- π exemplifies maximal entropy but minimal Kolmogorov complexity, highlighting the distinction between statistical and algorithmic randomness.
- Counting arguments show that most strings are incompressible (i.e., their shortest description is nearly as long as themselves), but it's impossible to pinpoint specific incompressible strings.
- Kolmogorov complexity is uncomputable: upper bounds can be found by discovering short programs, but lower bounds cannot be definitively established due to the halting problem and Berry paradox.
- Both compression types ultimately relate to the cost of differentiation—selecting one item from many possibilities—with entropy averaging this cost and Kolmogorov complexity applying it to individual objects.
- The asymmetry between finding compressibility (possible) and proving incompressibility (impossible) reflects deeper limitations in computation and proof.