Connections in Math: the two kinds of random
The article distinguishes two forms of lossless compression: statistical compression based on symbol frequencies and algorithmic compression based on short generating programs. It uses the example of a million random digits versus the first million digits of π, which are statistically indistinguishable yet differ in compressibility. The piece explains entropy as a measure of surprise and argues that statistical redundancy is not the sole source of compressibility.
- ▪A file of random digits and a file containing the first million digits of π have identical statistical distributions but differ in compressibility because π can be generated by a short program.
- ▪Statistical compression exploits uneven symbol frequencies, as captured by entropy, to reduce average message length.
- ▪Algorithmic compression relies on a concise description of the generating process, allowing compression even when symbol frequencies are uniform.
- ▪Entropy quantifies the average surprise of a source and sets the lower bound for lossless statistical compression.
- ▪The article concludes that compressibility can arise from both statistical redundancy and underlying algorithmic structure, not just the former.
Opening excerpt (first ~120 words) tap to expand
July 2, 2026 math Connections in Math: the two kinds of random Disclaimer: no AI was used to write this. Any errors, awkward sentences, and weird tangents are 100% organic, free-range, and human-made. Picking up a puzzle I left lying around Last post, right at the end, I dropped a puzzle and walked away from it. Here it is again, because this whole post is basically me refusing to let it go. Imagine two files, and each one holds a million digits. The first one is pure noise — imagine I rolled a ten-sided die a million times and wrote down the results. The second one is the first million digits of π\piπ. Now look at them the way a statistician would: count how often each digit from 000 to 999 shows up.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Stillthinking.
Discussion
0 commentsMore from Stillthinking
