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:

    “The conclusion suggested by these arguments might be called the paradox of theorizing. It asserts that if the terms and the general principles of a scientific theory serve their purpose, i. e., if they establish the definite connections among observable phenomena, then they can be dispensed with since any chain of laws and interpretive statements establishing such a connection should then be replaceable by a law which directly links observational antecedents to observational consequents.”
    —C.G. (Carl Gustav)

    “The rule is perfect: in all matters of opinion our adversaries are insane.”
    —Mark Twain [Samuel Langhorne Clemens] (1835–1910)

    “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)