nucleation

LIT-225: Minimum Description Length Induction, Bayesianism, and Kolmogorov Complexity

3 min read

Properties5
StatusActive — read 2026-10-14 (NOTE-801) in full; worth reading as the stated condition under which minimum description length and Bayes coincide: by the Fundamental Inequality (Theorem 3), Bayes code lengths and shortest-program lengths agree to within K(Pr(·|H)) + K(P) when the data are Martin-Löf random for the hypothesis and the hypothesis is random for the prior, so ideal MDL and MAP agree to a factor 2^{−α} among such hypotheses (Theorem 4), and for finite-set models both reduce to Kolmogorov's minimal sufficient statistic. Read it knowing that α can be as large as the hypothesis's own complexity, that admissibility cannot be checked, that "with high probability" (Corollary 1) and the overfitting claim are unproved, and that the arXiv text is the submitted version.
Version2
Tagslearning-theory, model-comparison, probabilistic-modeling, information-theory
Cited as “paper” byNOTE-203 — MDL induction, Bayesianism, and Kolmogorov complexity, NOTE-801 — Vitányi & Li — MDL induction, Bayesianism and Kolmogorov complexity
Cited as “source” byTHEORY-259 — For a recursive family of likelihoods and the universal prior, the Bayesian two-part code length −log Pr(D|H) − log m(H) equals the ideal-MDL length K(D|H) + K(H) plus the randomness deficiency of D for H, up to a constant fixed by the family; so ideal MDL and MAP selection agree to within a constant among hypotheses for which the data are random, and can part where they are not

Graph View

Paul M. B. Vitányi, Ming Li (1999), IEEE Transactions on Information Theory 46(2):446–464 (Mar 2000); first appeared as arXiv preprint (CWI Tech Report 1998) — arXiv:cs/9901014

Key takeaways

From the reading, NOTE-801.

  • The Fundamental Inequality (Theorem 3). For recursive Pr(·|·) and prior P, if D is Martin-Löf random for Pr(·|H) and H is random for P, then K(D|H) + K(H) − α ≤ −log Pr(D|H) − log P(H) ≤ K(D|H) + K(H), with α = K(Pr(·|H)) + K(P). Agreement to O(1) implies both randomness conditions.
  • Selection (Theorem 4). Among admissible hypotheses, those meeting both conditions, the ideal-MDL choice has posterior at least 2^{−α} times the MAP choice’s. With the universal prior every hypothesis is random for the prior. The condition is then that the data be random for the chosen hypothesis (Theorem 5).
  • The slack is not small in general. K(Pr(·|H)) ≤ K(H) + O(1), so for a complex hypothesis α is of the order of its whole description.
  • Where they diverge. Data 0ⁿ are atypical for a fair coin. If the coin is in fact fair, Bayes with a suitable prior can select it while MDL selects p = 0 (Remark 3). With two hypotheses, ideal MDL ties where Bayes chooses (Example 3).
  • Finite sets (Theorem 1). With uniform likelihood 1/d(H), Bayes under the universal prior, ideal MDL and Kolmogorov’s minimal sufficient statistic select the same set, to the O(1) in its definition.
  • Prediction (Theorems 7–8, Corollary 2). For μ-random sequences, M(y | x)/μ(y | x) → 1. The y maximising μ(y | x) is, with probability going to one, the one minimising Km(xy) − Km(x). The proof uses Gács’s result that −log M and Km agree on random strings and differ unboundedly in general.
  • What is not shown. Corollary 1’s “with high probability” has no stated measure or proof. The claim that Bayes overfits where MDL does not is called “some evidence” and is not demonstrated. Practical codes are out of scope (§2.6).

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-801. It is the record’s statement of when description length and Bayes agree. Theorems 3–4 are filed as THEORY-259: agreement only to within the complexity of the hypothesis’s likelihood, and only for data typical of the hypothesis.

Vereshchagin & Vitányi (LIT-239) later give the two-part code a guarantee for every string, with no typicality condition. Their §V-B(iii) shows that this paper’s K(H) + K(D|H) form can choose badly fitting models. Grünwald & Roos (LIT-238) leave Kolmogorov-complexity MDL to Grünwald’s 2007 book. It bears on THEORY-087 and CLAIM-154, which read the Bayesian Occam factor as a complexity penalty. A modeller’s prior matches the description-length penalty only for hypotheses random under it (NOTE-801, Bearing on the record).

Access when seeded: Read the arXiv abstract page (single version, submitted 1999-01-27) and the full 35-page PDF text: keywords, §2.1 (Def. 3, Thm 1), §2.4 (Thm 3), §2.6, §3 (Thms 7–8) and §4. I confirmed the published version’s DOI, volume, issue and pages through Crossref (no contact address sent). The arXiv text is the submitted version, so it may differ in detail from the journal article. Keywords are the paper’s own (the last one is truncated at the page break in the extracted text).

Backlinks