Source-linked AI summary
Proofs of conservation inequalities for Levin's notion of mutual information of 1974
Nikolay Vereshchagin
TL;DR
A prefix-based definition of infinite-sequence mutual information fails because prefixes can encode their length, making the resulting value infinite even for zero sequences. The paper develops conservation-test results and supporting proofs, including a probability- and expectation-bounded test for computable families of distributions.
Problem
A prefix-supremum definition can be infinite even for zero sequences because a prefix also identifies its length.
Source: §2 · p. 3Method
The paper proves conservation-test results, using a semimeasure argument to complete the proof for computable families of distributions.
Source: §3 · p. 8Results
For a computable family of distributions, each sequence pair has a probability- and expectation-bounded test.
Source: §3 · p. 8Takeaways & Limitations
The mutual-information definition is encoding invariant up to O(1) for sequences obtainable from each other by algorithmic operators.
Source: §3 · p. 7The conservation statement for algorithmic operators may fail when the operator's output is finite.
Source: §3 · p. 7
Abstract
from arXiv · showhide
In this paper we consider Levin's notion of mutual information in infinite 0-1-sequences, as defined in [Leonid Levin. Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory. Problems of information transmission, vol. 10 (1974), pp. 206--211]. 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.
1 Mutual information in finite strings
This section introduces mutual information for finite binary strings and states information-conservation results, including a test-based restatement of a theorem for computable probability measures.
1 Mutual information in finite strings
- The section defines mutual information for binary strings and uses K(x, y) for prefix complexity of a fixed computable encoding of the pair.The notation K(x) and K(x|y) denotes Kolmogorov prefix and conditional prefix complexity.Source: §1 · p. 1
- An algorithm A cannot increase mutual information with y by more than a constant: I(A(x) : y) ≤ I(x : y) + c_A.The claim applies when A(x) is defined.Source: §1 · p. 2
- For a distribution P on Z, a P-test t mapping Z to N is expectation bounded when E_P[2^{t(z)}] ≤ 1, and probability bounded when P(t(z) ≥ n) ≤ 2^{-n} for all n in N.By Markov's inequality, every expectation bounded P-test is probability bounded.Source: §1 · p. 2
- For a uniformly computable family of probability measures P_x, Theorem 2 is restated using an expectation-bounded P_x-test t_x,y,A for every x and y.The supplied passage does not include the restated test inequality.Source: §1 · p. 2
2 Mutual information in infinite binary sequences: the definition
The section defines Levin’s mutual information for infinite sequences through prefix information and explains why a supremum over equal-length prefixes is inadequate. It relates the definition to finite strings and analyzes the case of one finite and one infinite input.
2 Mutual information in infinite binary sequences: the definition
- Taking the supremum of mutual information between equal-length prefixes makes the proposed I1 infinite, even for all-zero sequences, because prefix length itself carries information.The section also notes that comparing only equal-length prefixes is problematic: stretching one sequence by inserting zeros changes the prefix length being compared.Source: §2 · p. 3
- The proposed I3 instead takes a supremum over independently chosen prefix lengths and subtracts K_α(n) and K_β(m) from the prefix mutual information.This proposal follows the section’s discussion of the length and equal-prefix problems.Source: §2 · p. 3
- Levin’s infinite-sequence mutual information takes a supremum over prefix pairs, subtracting their respective conditional prefix complexities K_α(x) and K_β(y).The section says this definition generalizes finite-string mutual information.Source: §2 · p. 3
- Compared with Definition 3, Levin’s definition replaces summation by a supremum and restricts x and y to prefixes; the section says summation matters for Theorem 6 and the full range for Theorem 5.Summation commutes with another summation, unlike maximization, according to the remark.Source: §2 · p. 3
- For coded finite strings ˜u and ˜v, Levin’s infinite-sequence mutual information equals I(u : v) up to O(1).The section says it supplies another proof, noting that gives no proof of this theorem and that proofs appeared in.Source: §2 · p. 3
- For u ∈ Ξ and β ∈ Ω, I(˜u : β) is at least K(u) − K_β(u) − O(1), but the converse fails generally and holds when 0′ Turing reduces to β.In all cases I(˜u : β) ≤ K(u) + O(1); for β=˜v and u=K(v), the gap can involve K(K(v)|v), which can be Ω(log n) for strings v of length n.Source: §2 · pp. 5–6
3 Information Conservation Inequalities for infinite sequences
The section presents the infinite-sequence information conservation inequalities and relates one to encoding invariance. For the probabilistic inequality, it gives a clarified test bound and a proof reduction using semimeasure domination.
3 Information Conservation Inequalities for infinite sequences
- Theorem 5 () is constrained to infinite outputs A(α): finite outputs may encode more information than α and can make the theorem's statement false.Source: §3 · pp. 6–7
- Theorem 5 makes Definition 3 encoding invariant up to O(1) for sequences mutually obtainable by algorithmic operators, including alternative encodings of sequence pairs.Source: §3 · p. 7
- For any probability distribution P computable relative to some sequence ρ, Theorem 6 () states that for every α, there is a probability-bounded P-test tα.Source: §3 · p. 7
- The clarified theorem gives each α a probability- and expectation-bounded test for an oracle-computable family Pρ, with cT independent of ρ, α, and ω.The proof reduces the bound to showing that the Pρ-expectation of mρ,ω(x) is at most dT mρ(x), using lower semicomputable semimeasure domination and swapping summation with integration.Source: §3 · p. 8
4 Mutual information and computability
Theorem 7 bounds mutual information with every β when α is computable and also gives a non-computable α whose mutual information with every β is bounded. The proof of the latter uses sequences whose prefix complexity stays within a constant of K(x).
4 Mutual information and computability
- Computable α has I(α : β) = O(1) for every β, but the converse fails because some non-computable α also have this bound.Source: §4 · p. 9
- For every β, Theorem 7 bounds I(α : β) by K(p) + O(1) when p computes α, and gives a non-computable α with I(α : β) ≤cα < ∞.The theorem’s second claim holds for all β.Source: §4 · p. 9
- The non-computable case uses sequences α with Kα(x) ≥ K(x)−c for a constant c independent of x, then repeats the argument from item (a).The passage points to for the existence of such sequences.Source: §4 · p. 9