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:

    “By this unprincipled facility of changing the state as often, and as much, and in as many ways as there are floating fancies or fashions, the whole chain and continuity of the commonwealth would be broken. No one generation could link with the other. Men would become little better than the flies of a summer.”
    —Edmund Burke (1729–1797)

    “Good taste is either that which agrees with my taste or that which subjects itself to the rule of reason. From this we can see how useful it is to employ reason in seeking out the laws of taste.”
    —G.C. (Georg Christoph)

    “In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
    —Marcel Proust (1871–1922)