nucleation

LIT-239: Kolmogorov's Structure Functions and Model Selection

3 min read

Properties6
StatusActive — read 2026-10-14 (NOTE-787) in full; worth reading as the theorem that, for a single string and every bound on model complexity, the set with the shortest two-part code is within O(log n) of the best-fitting set in randomness deficiency (Theorem IV.8), with the complete catalogue of shapes the structure functions can take and the proof that fit cannot be approximated while code length can. Read it knowing that every result holds only to O(log n), that the models are complexity-bounded finite sets or computable distributions and not statistical families, which the authors say the results do not transfer to directly, and that the construction proving Theorem D.2 was not checked line by line here.
Version2
Tagslearning-theory, information-theory, mathematics
SupportsCLAIM-289 — Non-stochastic strings stay non-stochastic under total recursive models: their minimal randomness deficiency agrees with the finite-set one to within O(log n) in argument and value
Cited as “paper” byNOTE-202 — Kolmogorov's structure functions and model selection, NOTE-787 — Vereshchagin & Vitányi — Kolmogorov's structure functions and model selection
Cited as “source” byTHEORY-244 — For a computable source distribution f, Shannon entropy and mutual information are the expectations of their Kolmogorov counterparts only to within the complexity of f: 0 ≤ E K(x) − H(f) ≤ K(f) + O(1), and I(X;Y) − K(f) − O(1) ≤ E I(x:y) ≤ I(X;Y) + 2K(f) + O(1); Grünwald and Vitányi's matching statement for the distortion-rate function rests on a step the record has not verified, THEORY-260 — An individual string's information splits non-trivially into structure and noise only in a model class without a universal member: with partial recursive models every string's minimal sufficient statistic is trivial, while with total recursive functions it is not, and the finite-set, computable-distribution and total-function classes agree to within logarithmic terms, THEORY-277 — For individual data, at every bound on model complexity, the model with the shortest two-part code is, to within O(log n), the best-fitting model in randomness deficiency, although the fit itself cannot be computed or approximated

Graph View

Nikolai K. Vereshchagin, Paul M. B. Vitányi (2002), IEEE Transactions on Information Theory 50(12):3265–3290 (Dec 2004); in part in Proc. 43rd IEEE FOCS 2002; first appeared as arXiv preprint — arXiv:cs/0204037

Key takeaways

From the reading, NOTE-787.

  • Code length finds fit (Theorem IV.8). For every string x of length n and every α, β_x(α) + K(x) ≅ λ_x(α) ≅ h_x(α) + α to within O(log n) in argument and value. Every set of complexity at most α + O(log n) that minimises K(S) + log |S| has deficiency within O(log n) of the best (Remark IV.10). The proof turns on δ(x | A) = Λ(A) − K(A | x*) − K(x) + O(1) and a counting lemma (Lemma C.4).
  • Not conversely. A best-fitting set need not have a short two-part code, except at the “critical” complexities where λ_x is still falling (Remark IV.10, Theorem IV.11).
  • All shapes occur (Theorem IV.4, Corollary IV.9). Any non-increasing λ with λ(0) ≤ n and λ(k) = k is λ_x for some x, to logarithmic precision. So non-stochastic strings exist at every length and complexity. For α₀ + β₀ < n − O(log n), some string is not (α₀, β₀)-stochastic, which strengthens Shen’s result.
  • The worst-case data code matters. The guarantee is for K(S) + log |S|. Minimising K(A) + K(x | A), “ultimate compression”, can pick a model of deficiency n/2 when n/4 is achievable (§V-B(iii)).
  • Computability (§VII, App. D).
    • h_x and λ_x are upper semicomputable but not approximable within |x|/(10 log |x|), even given K(x).
    • β_x is neither lower nor upper semicomputable within large margins.
    • No algorithm finds the minimal sufficient statistic from x and K(x).
    • Given that statistic’s complexity, λ_x is computable (Muchnik, Theorem D.5).
  • Scope. Finite-set models, with computable distributions and total recursive functions equivalent to within O(log n) (Appendix B). The authors say parametric statistical classes are “partially poorer and partially richer” and that the results “cannot be directly transplanted” to them.

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-787. It is the record’s technical core for that heading. Its main result is filed as THEORY-277: within a complexity-bounded class, the shortest two-part code finds the best-fitting model for the individual datum, to O(log n), while the fit itself is uncomputable.

Grünwald & Vitányi (LIT-224) restate it and relate its expectation to Shannon’s distortion-rate function. Vitányi & Li (LIT-225) reach ideal two-part MDL from Bayes’s rule, and this paper’s §V-B(iii) shows why the data part should be log |S| rather than K(x | S). The reading bears on CLAIM-152 by giving a sufficiency with no target variable, which is still not a unique boundary, and on QUESTION-040, as a description-length Occam term (NOTE-787, Bearing on the record). Its O(log n) precision is the same order as the parametric penalties of THEORY-087, so it cannot speak to them.

Access when seeded: Identified from the Semantic Scholar link by title, then found on arXiv (v1 2002-04-16, v5 2004-08-05 = final journal version). Read the arXiv abstract page and the full v5 PDF text: §III overview, §IV theorem statements, §V (MDL, ML, non-stochastic objects), §VII, and Appendix I (oral history). I confirmed the DOI, volume, issue and pages through Crossref (no contact address sent). The arXiv comment says “Proc 47th IEEE FOCS”, but FOCS 2002 was the 43rd; I have not verified which is right, so the FOCS number is unverified. The footnote on p. 1 of v5 also says “47th”.

Backlinks