Kolmogorov Complexity

In the previous chapter, we saw what entropy tells us about compressing strings. If we treat letters independently, coding theory is especially powerful. But that's an assumption that good compression algorithms can't make.

Kolmogorov complexity is the ultimate limit for how much a file can be compressed. This makes it a very powerful theoretical concept to have in our dictionary!

The Mandelbrot Set

Take a good look at the following picture.¹ It shows a so called Mandelbrot set -- we color each pixel of the plane based on how quickly a certain sequence of numbers shoots to infinity.

If you take print screen of this picture and save it on your disk, it's going to take a few MB. But what if you instead save the instruction for how to create this image? All relevant ingredients are stored in the two boxes below the picture - the formula used to create it, and the coordinates of the plane you are looking at. We are talking about less than kilobyte of memory now.

This is the gist of Kolmogorov complexity. For any given object - say, represented as a binary string - it's Kolmogorov complexity is the length of the shortest program that prints that string.

Here are a few more examples.

• Although digits of $\pi$ have many random-like properties, the Kolmogorov complexity of its first million digits is extremely small. That's because there are some extremely short programs printing it.
• Larger numbers (written down in binary) typically have larger Kolmogorov complexity. But there are huge numbers like with very small Kolmogorov complexity.
• Whenever you can ZIP a file to a size of 100MB, you can say that "Kolmogorov complexity of the file is at most 100MB"
• The Hutter's challenge from coding theory chapter is about estimating the Kolmogorov complexity of 1GB of Wikipedia
• If you keep flipping a coin $n$ times, the resulting sequence is likely to have Kolmogorov complexity of about $n$. There's no good way of compressing it.

Choosing the language

There is an awkward problem with the definition of Kolmogorov complexity. It's the length of the shortest program -- but what programming language do we use? Python? C? Assembly? Turing machine? Do we allow languages and libraries? Printing million digits of $\pi$ can then reduce to this:

import sympy
print(sympy.N(sympy.pi, 1000000))

The important insight is that, at least if we stay on the theoretical side of things, the choice does not matter that much. The trick is that in any (Turing-complete) programming language, we can build an interpreter of any other programming language. Interpreter is a piece of code that reads a code written in some other language, and executes its instructions.

In any reasonable programming language, you can write an interpreter for any other reasonable language in at most, say, 1MB. But this means that Kolmogorov complexity of any object is fixed 'up to 1MB': If you have a 100MB Python script that prints the file, then you have a 101MB C, Assembly, Java, ... script printing the same file - just write a code where the first 1MB is an interpreter of Python tasked to execute the remaining 100MB.

So for large objects (like the 1GB Wikipedia file from Hutter's prize), there's nothing awkward in using Kolmogorov complexity. The flip side is that it's pretty meaningless to argue whether the Kolmogorov complexity of $\pi$ is 200 or 300 bytes. That difference depends on the choice of programming language too much.

Kolmogorov vs entropy: $E[K(x)] \approx H(X)$

Both Kolmogorov complexity and entropy are trying to measure something very similar: complexity, information, compression limit. Naturally, there are closely connected. The connection goes like this: If you have a reasonable distribution ($X$) over bit strings and you sample from it ($x$), then the entropy of the distribution is roughly equal to the expected Kolmogorov complexity of the sample. I.e., .

print('01000...010110')

If you look at above proof sketch, you can notice that we did not really use that the distribution is uniform, it works pretty much for any distribution.³

However, the case of a uniform distribution is the most interesting: It tells us that most $n$-bit strings can't really be compressed, since their Kolmogorov complexity is close to $n$! In fact, $n$-bit strings with Kolmogorov complexity $\ge n$ are called Kolmogorov random, to highlight the insight that bits are random if we can't compress them.

Solomonoff prior & induction

What's the most natural distribution over all (finite) binary strings, if what we care about is their Kolmogorov complexity? The maximum entropy principle says we should consider the distribution , for some $\lambda$. In a minute, we will see that the right $\lambda$ is such that $p(x) \propto 2^{-K(x)}$ ⁴ This distribution is called Solomonoff prior. ⁵

It's called prior because this is how we typically want to use this distribution. Similarly to other maximum entropy distributions, this is where should start before we start making observations and updating it. I find it philosophically very appealing, feel free to check the expand boxes.