Proofs of conservation inequalities for Levin's notion of mutual information of 1974

In this paper we consider Levin's notion of mutual information in infinite 0-1-sequences, as defined in Levin (1974) [6]. The respective information conservation inequalities were stated in that paper without proofs. Later some proofs appeared in the literature, however no proof of the probabilistic conservation inequality has been published yet. In this paper we prove that inequality and for the sake of completeness we present also short proofs of other properties of the said notion. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

In this paper, we consider Levin's notion of mutual information in infinite 0-1-sequences and prove the probabilistic conservation inequality. Additionally, we provide brief proofs of other properties of this notion for completeness.