Kolmogorov complexity
Shannon entropy measures the information in a random source: how many binary digits, on average, its outcomes need. Kolmogorov complexity measures the information in one string: the length of the shortest program that prints it. This page defines Kolmogorov complexity, shows that most strings cannot be compressed and that no program computes it, and shows that its expected value per symbol approaches the entropy. It builds on the entropy and source coding pages in Information Theory for Data Science.
1 Shortest descriptions
Proof. Because \(U\) is universal, some program \(s_A\) makes \(U\) simulate \(A\): given \(s_A\) followed by a program \(p\) for \(A\), \(U\) outputs whatever \(A\) outputs on \(p\). So if \(p\) is a shortest program for \(x\) on \(A\), then \(s_A\) followed by \(p\) is a program for \(x\) on \(U\), and \(K_U\mathopen{}\left(x\right)\mathclose{} \le {\mathopen{}\left|s_A\right|\mathclose{}} + {\mathopen{}\left|p\right|\mathclose{}} = K_A\mathopen{}\left(x\right)\mathclose{} + {\mathopen{}\left|s_A\right|\mathclose{}}\). The same program \(s_A\) also passes \(n\) on to \(A\), which gives the conditional bound in the same way. Take \(c_A = {\mathopen{}\left|s_A\right|\mathclose{}}\). Cover and Thomas (2006, sec. 14.2) give this argument in full.
Proof. For the first bound, the program “print the next \(n\) digits” followed by the \(n\) digits of \(x\) outputs \(x\). Because \(U\) is given \(n\), the program needs no marker to show where it ends, and its fixed part has some length \(c_1\). So \({K\mathopen{}\left(x \mid n\right)\mathclose{}} \le n + c_1\).
For the second bound, the program must also describe \(n\) in a way that shows where the description ends. Write \(n\) in binary, which takes \(\mathopen{}\left\lfloor\log_2 n\right\rfloor\mathclose{} + 1\) digits, repeat each digit twice, and end with the pair \(01\). This takes \(2 \mathopen{}\left\lfloor\log_2 n\right\rfloor\mathclose{} + 4 \le 2 \log_2 n + 4\) digits. A program that reads this description of \(n\) and then prints the next \(n\) digits has length at most \(n + 2 \log_2 n + 4 + c_2\) for a constant \(c_2\). Take \(c = \max(c_1, c_2 + 4)\). Cover and Thomas (2006, sec. 14.2) prove both bounds.
2 Incompressible strings
Proof. There are \(2^j\) binary strings of length \(j\), so the number of programs of length less than \(n - k\) is
\[\sum_{j=0}^{n-k-1} 2^j = 2^{n-k} - 1,\]
where the sum is empty, and equal to \(0\), when \(k = n\).
Given \(n\), each program outputs at most one string, so at most \(2^{n-k} - 1\) strings \(x\) have a program shorter than \(n - k\). With \(k = 0\), at most \(2^n - 1\) of the \(2^n\) strings of length \(n\) have \({K\mathopen{}\left(x \mid n\right)\mathclose{}} < n\), which leaves at least one with \({K\mathopen{}\left(x \mid n\right)\mathclose{}} \ge n\).
3 Kolmogorov complexity is uncomputable
Proof. Suppose a program \(Q\) halts on every binary string \(x\) and outputs \({K\mathopen{}\left(x\right)\mathclose{}}\). For each integer \(m \ge 1\), consider the program \(P_m\) that does the following: list binary strings in order of length, and in lexicographic order within each length, use \(Q\) to compute \({K\mathopen{}\left(x\right)\mathclose{}}\) for each one, and output the first \(x\) with \({K\mathopen{}\left(x\right)\mathclose{}} \ge m\). Such an \(x\) exists, because fewer than \(2^m\) programs are shorter than \(m\), so \(P_m\) halts, and its output \(x\) has \({K\mathopen{}\left(x\right)\mathclose{}} \ge m\).
The program \(P_m\) consists of a fixed part, of some length \(c\), and a description of \(m\) that shows where it ends, which the proof of Theorem 2 writes in at most \(2 \log_2 m + 4\) digits. So the output \(x\) of \(P_m\) also has \({K\mathopen{}\left(x\right)\mathclose{}} \le 2 \log_2 m + 4 + c\), and together
\[m \le {K\mathopen{}\left(x\right)\mathclose{}} \le 2 \log_2 m + 4 + c.\]
The left side grows faster than the right, so this fails once \(m\) is large enough, and no such \(Q\) exists. The argument formalizes the Berry paradox, “the smallest positive integer not definable in under sixty letters”, and Cover and Thomas (2006, chap. 14) discuss why \(K\) cannot be computed.
4 Kolmogorov complexity and entropy
Proof. For the lower bound, send each outcome \(x^n\) of \(X^n\) to a shortest program that outputs it given \(n\). Different outcomes get different programs, because a program determines its output, and no halting program is a prefix of another, so this is a prefix code for \(X^n\), which makes it uniquely decodable. Its expected length is \({\mathbb{E}\mathopen{}\left[{K\mathopen{}\left(X^n \mid n\right)\mathclose{}}\right]\mathclose{}}\). If \(X\) takes only one value with positive probability, then \({H\mathopen{}\left(X\right)\mathclose{}} = 0\) and the lower bound holds trivially. Otherwise, \(X^n\) also takes at least two values with positive probability, and part 1 of the source coding theorem gives \({\mathbb{E}\mathopen{}\left[{K\mathopen{}\left(X^n \mid n\right)\mathclose{}}\right]\mathclose{}} \ge {H\mathopen{}\left(X^n\right)\mathclose{}}\). Applying the chain rule for entropy \(n - 1\) times, and using that conditioning on independent variables does not change entropy, gives \({H\mathopen{}\left(X^n\right)\mathclose{}} = n {H\mathopen{}\left(X\right)\mathclose{}}\). Dividing by \(n\) gives the lower bound.
For the upper bound, Cover and Thomas (2006, sec. 14.3) describe \(x^n\) in two parts: first how many times each value in \(\mathcal{X}\) occurs, which takes about \((\mathopen{}\left|\mathcal{X}\right|\mathclose{} - 1) \log_2 n\) digits, then which of the strings with those counts \(x^n\) is, which takes about \(n {H\mathopen{}\left(X\right)\mathclose{}}\) digits on average.