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 00 to 99 shows up. In both files, every digit appears about a tenth of the time, so if you plot the two histograms you cannot tell them apart — both flat, both featureless. And you can run any “is this random?” test you like, because both files will pass. By every statistical measure, these two files are the same: both look like pure, incompressible randomness.

And yet. One of these files I can send you in three lines. I write you a tiny program — “compute π\pi, print a million digits” — and you regenerate the file exactly. The other file I cannot shrink at all, and to send it to you I have to send the whole thing, digit by digit, because there is no shorter description of it than itself. So here is the entire post in one question:

If the two files are statistically identical, why can I compress one and not the other?

The thing is, this question does not have a simple answer, and I think that is exactly what makes it interesting. To get anywhere with it, we have to be careful about what the word “compressible” actually means — and once we are careful, it splits into two very different ideas. Most of this post is about pulling those two apart, and about a surprise waiting at the end of the second one: a kind of compressibility that you can always confirm when it is there, but can never rule out when it is not.

Two kinds of compression One thing I want to be clear about from the start: everything in this post is about lossless compression, which means nothing is thrown away and nothing is approximated — I send you a shorter description, and you rebuild the exact original from it, bit for bit. Even with that strict rule, I think there are really two different reasons a thing can be compressible, and this post is mostly about learning to tell them apart. The first reason is statistical. Some symbols appear more often than others, so you give the common ones short codes and the rare ones long codes, and on average you save space. This is what zip files and Huffman coding do, and I think it is the kind of compression most people have in mind when they hear the word. The second reason is about the process. The thing might come from a simple rule — a short program — even when its symbols look perfectly evenly spread out. In that case there is no statistical redundancy to exploit at all, and yet the thing still compresses, because the shortness lives in the process that generates it, not in the frequencies of its symbols. So the real question of this post is: is statistical redundancy the only kind of compressibility there is? And π\pi is about to say no. The statistical kind: entropy Building entropy from a budget Before we can say what is strange about π\pi, we need to pin down what “statistical compression” even measures, and the measure has a name: entropy. Informally, entropy is the average amount of surprise in a source of symbols. If a source always emits the same symbol, there is no surprise at all — you already know what is coming, so each new symbol tells you nothing, and the entropy is zero. If a source emits ten different digits with equal probability, every new symbol is as surprising as it can be, and the entropy is maximal. Most sources live somewhere in between: some symbols are common (little surprise, little information) and some are rare (big surprise, more information), and entropy is the average over all of them, weighted by how often each one shows up. The connection to compression is direct: surprise is exactly the thing you have to pay bits for. Whatever is predictable you can leave out, because the receiver can fill it in, and whatever is surprising you have to actually transmit.

The ideal length of a codeword for a symbol of probability pp is log2(1/p)\log_2(1/p) bits, so common symbols (pp near 1) get lengths near zero, and rare symbols (pp tiny) get long ones. This is exactly the intuition we started with, but now with a number on it. And here is the part I like most: you can see the average message length as an area. Put each symbol’s probability on one axis and its codeword length log2(1/p)\log_2(1/p) on the other, so that each symbol becomes a rectangle of area p⋅log2(1/p)p \cdot \log_2(1/p), and the total area is the average number of bits per symbol: H=∑ipilog21pi  =  −∑ipilog2pi.H = \sum_i p_i \log_2\frac{1}{p_i} \;=\; -\sum_i p_i \log_2 p_i.That is Shannon entropy, and it is the smallest possible area — the shortest average message any code can achieve for this distribution. If you give a common symbol a long codeword you add a lot of area, and the budget rule is exactly what removes that waste.

(There is a second way to read log2(1/p)\log_2(1/p) that is worth keeping in your pocket: it is the number of yes/no questions — halvings — that you need to isolate something occupying a pp-fraction of the possibilities. A rare thing needs many halvings, a common thing needs few. Same number, two lenses.) To feel it on a clean case, take four symbols with probabilities 12,14,18,18\tfrac12, \tfrac14, \tfrac18, \tfrac18. The formula hands out ideal lengths of 1,2,3,31, 2, 3, 3, and you can actually build those codewords: 0, 10, 110, 111, with no prefixes colliding.

The average length is 12(1)+14(2)+18(3)+18(3)=1.75\tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 bits, which is exactly HH. The most common symbol got the one-bit codeword, the rare ones paid in length, and the budget balanced perfectly. And here is the fact our puzzle needs: entropy is largest when everything is equally likely. A uniform distribution over ten digits maxes out at log210≈3.32\log_2 10 \approx 3.32 bits per digit, because there is no frequent symbol to buy a cheap codeword for. Both of our files are uniform, so both have maximal entropy, which means that statistically, both are as incompressible as a thing can be. Entropy’s blind spot Now I want to show what entropy cannot see. Entropy looks only at the distribution of symbols — how often each one appears. It never looks at their order, and it never looks at whether there is a rule generating them. You can take any structured sequence and shuffle it: the histogram does not change, so the entropy does not change, but you have destroyed whatever pattern a program could have used. Entropy did not notice anything, because it never saw the pattern in the first place. And that is the crack π\pi slips through. Its digits have maximal entropy because, symbol by symbol, they are uniform. But π\pi is not made by rolling dice. π\pi is made by a rule — a short, fixed, deterministic rule that a program can carry out — and entropy is blind to that rule, because the rule leaves no fingerprint in the digit frequencies. So we need a second notion of compressibility, one that can see rules. The process kind: Kolmogorov complexity Here it is, and it is very simple:

The Kolmogorov complexity K(x)K(x) of a string is the length of the shortest program that outputs it.

Not the average of anything, not a distribution — one string, one shortest program. A string of a billion zeros has tiny complexity, because print "0" a billion times is a very short program.

A truly random string of length nn has complexity of about nn, because no description is shorter than the string itself, so the “program” is basically “print the whole thing”. And π\pi? Tiny — a couple hundred bits, because a small program grinds out its digits forever. So the puzzle resolves, and the resolution is that we were holding two different rulers:

Shannon entropy is statistical. It is about an ensemble — a source, a distribution, the long run — and it sees frequencies, nothing else. Kolmogorov complexity is structural. It is about one object, and it sees rules, structure, generating processes.

π\pi is the object where the two rulers disagree as loudly as possible: maximal entropy, minimal complexity. Statistics says “random, cannot compress”, and Kolmogorov says “trivial, here is a five-line program”. Both are right, because they are answering different questions.

There is a bridge between the two, though: for a truly random source, the expected Kolmogorov complexity of its outputs equals its Shannon entropy, up to a small constant. So on average, over a whole distribution, the two rulers agree, and I like to think of statistics as the shadow that algorithmic structure casts when you only look at ensembles. The two only come apart for individual, special objects that hide a generating rule, and π\pi is the extreme case of that. But most objects are not special at all — and that is the next thing, because it is the one thing here that you can actually prove. Almost nothing can be compressed Here is a claim that sounds hard and is actually a subtraction:

Almost every string is its own shortest description. Most things cannot be compressed at all.

Watch. Fix a length nn and ask: how many strings of length exactly nn are there? Two choices per position, nn positions, so 2n2^n of them. Now ask: how many possible descriptions are shorter than nn — that is, programs of length 0,1,2,…,n−10, 1, 2, \dots, n-1? Adding them up gives 1+2+4+⋯+2 n−1=2n−1,1 + 2 + 4 + \dots + 2^{\,n-1} = 2^n - 1,which is one fewer than the number of strings.