Chain rule for Kolmogorov complexity

The chain rule for <a href="/facts/Kolmogorov_complexity/L9ezq8pY">Kolmogorov complexity</a> is an analogue of the chain rule for <a href="/facts/Information_entropy/NLg4NLvt">information entropy</a>, which states:

H
        (
        X
        ,
        Y
        )
        =
        H
        (
        X
        )
        +
        H
        (
        Y
        
          |
        
        X
        )
      
    
    {\displaystyle H(X,Y)=H(X)+H(Y|X)}

That is, the combined <a href="/facts/Randomness/QJQBoEX5">randomness</a> 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 <a href="/facts/Conditional_entropy/gHzPezGB">conditional</a> and <a href="/facts/Joint_entropy/V4WwuX6P">joint entropy</a>, and the fact from <a href="/facts/Probability_theory/mFBn51rE">probability theory</a> that the <a href="/facts/Joint_probability/klX2ksGY">joint probability</a> is the product of the <a href="/facts/Marginal_probability/U9XBWAd1">marginal</a> and <a href="/facts/Conditional_probability/QcN2UERV">conditional probability</a>:

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

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

The equivalent statement for Kolmogorov complexity does not hold exactly; it is true only up to a <a href="/facts/Logarithm/QeXaV97q">logarithmic</a> term:

K
        (
        x
        ,
        y
        )
        =
        K
        (
        x
        )
        +
        K
        (
        y
        
          |
        
        x
        )
        +
        O
        (
        log
        ⁡
        (
        K
        (
        x
        ,
        y
        )
        )
        )
      
    
    {\displaystyle 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 <a href="/facts/Big-O_notation/weFFjSWg">at most</a> a logarithmic factor. The results implies that <a href="/facts/Mutual_information/HIUvsjvV">algorithmic mutual information</a>, an analogue of mutual information for Kolmogorov complexity is symmetric: ⁠
 
 
 
 I
 (
 x
 :
 y
 )
 =
 I
 (
 y
 :
 x
 )
 +
 O
 (
 log
 ⁡
 K
 (
 x
 ,
 y
 )
 )
 
 
 {\displaystyle I(x:y)=I(y:x)+O(\log K(x,y))}
 
⁠ for all x,y.

Chain rule for Kolmogorov complexity open-in-new

Chain rule for Kolmogorov complexity