Chain rule for Kolmogorov complexity

${\displaystyle P(X,Y)=P(X)P(Y|X)}$

${\displaystyle \Rightarrow \log P(X,Y)=\log P(X)+\log P(Y|X)}$

Proof

The ≤ direction is obvious: we can write a program to produce x and y by concatenating a program to produce x, a program to produce y given access to x, and (whence the log term) the length of one of the programs, so that we know where to separate the two programs for x and y|x (log(K(x, y)) upper-bounds this length).

For the ≥ direction, it suffices to show that for all k,l such that k+l = K(x,y) we have that either

K(x|k,l) ≤ k + O(1)

or

K(y|x,k,l) ≤ l + O(1).

Consider the list (a₁,b₁), (a₂,b₂), ..., (a_e,b_e) of all pairs (a,b) produced by programs of length exactly K(x,y) [hence K(a,b) ≤ K(x,y)]. Note that this list

• contains the pair (x,y),
• can be
  enumerated
  given k and l (by running all programs of length K(x,y) in parallel),
• has at most 2^K(x,y) elements (because there are at most 2ⁿ programs of length n).

First, suppose that x appears less than 2^l times as first element. We can specify y given x,k,l by enumerating (a₁,b₁), (a₂,b₂), ... and then selecting (x,y) in the sub-list of pairs (x,b). By assumption, the index of (x,y) in this sub-list is less than 2^l and hence, there is a program for y given x,k,l of length l + O(1). Now, suppose that x appears at least 2^l times as first element. This can happen for at most 2^K(x,y)-l = 2^k different strings. These strings can be enumerated given k,l and hence x can be specified by its index in this enumeration. The corresponding program for x has size k + O(1). Theorem proved.

References