Peter D. Grünwald, Paul M. B. Vitányi (2004), arXiv preprint (survey; the arXiv comment says “Submitted to IEEE Trans Information Theory”) — arXiv:cs/0410002
Key takeaways
From the reading, NOTE-776.
- Entropy (Theorem 2.10). For computable f, 0 ≤ Σ f(x)K(x) − H(f) ≤ K(f) + O(1). The gap is O(1) when f is given to the machine. It is unbounded for complex sources: a point mass on one complex string has entropy 0.
- Mutual information (Theorem 3.6, Lemma 3.7). I(X;Y) − K(f) < E I(x : y) < I(X;Y) + 2K(f). Algorithmic mutual information is never negative, where pointwise Shannon information can be (Example 3.1).
- Data processing (Theorems 4.4, 4.6). Deterministic processing raises algorithmic mutual information by at most the processor’s complexity. Randomised processing raises it by d bits with probability O(2
- Sufficiency (Proposition 5.3, Remark 5.11, Theorem 5.13). The individual, expectation and mutual-information definitions of sufficiency are equivalent only when exact. An algorithmic sufficient statistic is nearly sufficient in expectation for every computable model, uniformly only if model complexity is bounded. No converse is given.
- Structure function (§6.2, Remark 6.14). This restates Vereshchagin & Vitányi (LIT-239). “ML = MDL” only under a fixed complexity bound, and MDL overfits like ML unless it prefers the least complex model on the flat stretch of λ_x.
- Distortion–rate (Theorem 6.27). (1/m) E h_x(mR + K(f, d, m, R) + O(log n)) ≤ D_m(R) ≤ (1/m) E h_x(mR), with limit D(R). The authors call it a sanity check for noise-like data. One step of the proof is asserted.
- Caveat. The arXiv record warns: “There are some errors in this paper draft; when in doubt see the textbook Li, Vitanyi”. The reading found garbled arithmetic in Examples 6.13 and 6.16.
Standing in the record
Filed on 2026-09-26 at the owner’s request, from a list they grouped under the heading Relating K-complexity to minimum sufficient statistics. Read on 2026-10-14 in NOTE-776. It is the record’s bridge between Shannon and Kolmogorov quantities, and the stated size of each gap. Its bridge theorems are filed as THEORY-244: the identifications hold only to within the complexity of the source. Its §6.2 restates the result of LIT-239, filed as THEORY-277.
NOTE-241 and NOTE-300 cite it, both correctly: for the difference between a distribution’s entropy and one file’s description length, and for the pairing of rate–distortion with the structure function. It agrees with THEORY-238’s line that a coding rate under a prior is not Kolmogorov complexity.
Access when seeded: Identified from the Semantic Scholar link by title and arXiv id. Read the arXiv abstract page (single version, submitted 2004-10-01) and the full 54-page PDF text: contents, overview §1.1, §2.3, §5.2–5.3, §6 opening, §6.3.4 and §7. The arXiv record carries an authors’ warning: “There are some errors in this paper draft; when in doubt see the textbook Li, Vitanyi”. I found no journal publication of this exact text, so doi is none. A related shorter piece by the same authors exists, but I did not verify or read it.