Connections in Math: the two kinds of random

Comments

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 π.

Now look at them the way a statistician would: count how often each digit from 0 to 9 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 π, 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 π is about to say no.

The statistical kind: entropy

Building entropy from a budget

Before we can say what is strange about π, 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 symbols should get short codewords; rare symbols can afford long ones, since I'll rarely send them. That's the whole intuition and it's obviously right. The real question is: exactly how short, for a symbol that appears with probability p?

Here's the catch that turns it into a real question. Codewords compete. To decode a stream unambiguously, no codeword can be a prefix of another - if 0 is a codeword, nothing else may start with 0. So handing out a short codeword is expensive: it eats a big chunk of the space of codewords still available. Precisely, a codeword of length L costs a 2^(-L) slice of that space - a 1-bit codeword burns half of everything, a 2-bit codeword a quarter, and so on. Short codewords are a scarce resource, and spending on one forces the others to grow.

Think of it as a fixed budget. Every symbol has to buy a codeword, and short codewords cost more. So how do you spend a fixed budget across your symbols? The natural move - and it turns out to be the optimal one - is to spend on each symbol in proportion to how often you use it: give a symbol of probability p a p-sized slice of the budget. A slice of size p buys a codeword of cost 2^(-L), i.e. 2^(-L) = p, which means L = -log₂(p).

And there it is - not asserted, but derived. The ideal length of a codeword for a symbol of probability p is -log₂(p) bits, so common symbols (p near 1) get lengths near zero, and rare symbols (p 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 on the other, so that each symbol becomes a rectangle of area p × -log₂(p), and the total area is the average number of bits per symbol:

H = Σ p × -log₂(p)

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 H that is worth keeping in your pocket: it is the number of yes/no questions - halvings - that you need to isolate something occupying a p-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 1/2, 1/4, 1/8, 1/8. The formula hands out ideal lengths of 1, 2, 3, 3, and you can actually build those codewords: 0, 10, 110, 111, with no prefixes colliding. The average length is 1.75 bits, which is exactly H. 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 log₂(10) ≈ 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 be careful, because there is a subtlety here that is easy to get wrong. Entropy is really a property of a source - a process that emits symbols with certain probabilities - and not of a single fixed sequence. Strictly speaking there is no such thing as "the entropy of π"; π is just one sequence, and a lone sequence does not come with probabilities attached.

So what are we actually doing when we "measure the entropy" of one of our files? We count how often each digit appears, treat those frequencies as if they came from a source that emits digits independently, and compute the entropy of that source. And this is exactly where the blindness enters: the moment we summarize a sequence by its frequencies, we have thrown away its order, so any sequence with the same digit frequencies looks identical to us - the ordered ones and the patternless ones alike.

π and the noise file give the same frequencies, so this frequency-based estimate calls them equally random, even though one of them is generated by a dead-simple rule. The rule is not invisible to all of statistics - if you knew the right source, you could describe π's process and its entropy would be tiny. The point is narrower: with a single sequence in hand and nothing but its frequencies, the generating rule leaves no trace.

What we need is a measure defined for the individual object, one that does not need a source at all. That is exactly what Kolmogorov complexity is.

The process kind: Kolmogorov complexity

Here it is, and it is very simple: The Kolmogorov complexity 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 n has complexity of about n, because no description is shorter than the string itself, so the "program" is basically "print the whole thing". And π? 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.

π 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 π 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 n and ask: how many strings of length exactly n are there? Two choices per position, n positions, so 2^n of them. Now ask: how many possible descriptions are shorter than n - that is, programs of length < n? Adding them up gives 2^n - 1, which is one fewer than the number of strings.

That is the whole argument. There are 2^n strings and only 2^n - 1 shorter descriptions, so even in the most generous world imaginable - where every short description is used and each one points at a different string - you can cover at most 2^n - 1 of them, which means at least one string of length n has no description shorter than itself.

And if you push the same counting a little further, the situation gets much worse. Suppose you want real compression, a description at least k bits shorter. There are only about 2^(n-k) descriptions that short, so at most a fraction 2^(-k) of all strings can be compressed by k bits. If you want to save 10 bits, at most one string in a thousand can do it, and if you want to save 20 bits, it drops to one in a million. So deep compression is not just rare - it becomes exponentially more rare the more you ask for.

There is something about the shape of this argument that I want to point out, because it comes back again later: we just proved that incompressible strings are almost all of them without ever naming a single one. It is like counting doors and counting keys and realizing there are not enough keys - we know some door has to stay locked, but the counting never tells us which one, because we never actually opened any door.

There is also a move hiding inside the counting that is worth saying out loud: a program is itself a string. This is the only reason we could put "number of strings" and "number of programs" side by side and subtract, because they are the same kind of object, measured in the same bits. I think this simple fact is what the rest of the post depends on, so hold onto it.

One more thing this counting settles. When I first understood this argument, I tried to be clever and dodge it. What if I don't store the string itself, but its index in the list of all strings? Or what if I write a short program that generates many strings from a seed, and I just store the seed? It turns out every scheme like this fails in the same way, and the reason is always the same: To select one specific thing from a family of size N, you need a name that can tell N things apart, and a name that distinguishes N possibilities costs about log₂(N) bits. An index into 2^n strings is a number that takes n bits to write down, so there are no savings. A seed that picks one