Connections in Math: the two kinds of random. --><br>← all posts 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. 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. So the entropy of a source, measured in bits per symbol, is the size of the shortest average message you can ever hope to achieve — it is the floor that no lossless code can go below.

That is the informal picture. But I don’t want to just state the formula and move on, because there is a way to actually derive it, and I am borrowing the spirit of it from Chris Olah’s lovely Visual Information Theory — the pictures below are my own version of his argument.

Here’s the setup. I want to send you a stream of symbols using as few bits as possible, by giving each symbol a codeword — a little string of bits. Common...