Chain Rule For Kolmogorov Complexity

Chain Rule For Kolmogorov Complexity

The chain rule for Kolmogorov complexity is an analogue of the chain rule for information entropy, which states:

H(X,Y) = H(X) + H(Y|X)

That is, the combined randomness of two sequences X and Y is the sum of the randomness of X plus whatever randomness is left in Y once we know X. This follows immediately from the definitions of conditional and joint entropy fact from probability theory that the joint probability is the product of the marginal and conditional probability:

P(X,Y) = P(X) P(Y|X) \,

The equivalent statement for Kolmogorov complexity does not hold exactly; it is true only up to a logarithmic term:

K(x,y) = K(x) + K(y|x) + O(\log(K(x,y)))

(An exact version, KP(x, y) = KP(x) + KP(y|x*) + O(1), holds for the prefix complexity KP, where x* is a shortest program for x.)

It states that the shortest program printing X and Y is obtained by concatenating a shortest program printing X with a program printing Y given X, plus at most a logarithmic factor. The results implies that algorithmic mutual information, an analogue of mutual information for Kolmogorov complexity is symmetric: I(x:y) = I(y:x) + O(log K(x,y)) for all x,y.

Read more about Chain Rule For Kolmogorov Complexity:  Proof

Famous quotes containing the words chain, rule and/or complexity:

    “From Nature’s chain whatever link you strike,
    Tenth or ten thousandth, breaks the chain alike.”
    —Alexander Pope (1688–1744)

    “Man who man would be,
    Must rule the empire of himself; in it
    Must be supreme, establishing his throne
    On vanquished will, quelling the anarchy
    Of hopes and fears, being himself alone.”
    —Percy Bysshe Shelley (1792–1822)

    “The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
    —Jean Baudrillard (b. 1929)