Metraipolis › archive › dc_126e9569f712

Kolmogorov structure function — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Kolmogorov_structure_function
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T22:08:42.497Z
SHA-256 of the archived text: 0f75fa152c79e5d5b9097cbb9597e5617fe99136599267f01e8d94d81bea0a00
Stable URL of this page: https://metraipolis.com/documento/dc_126e9569f712

How to cite

Kolmogorov structure function — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Kolmogorov_structure_function (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_126e9569f712 (Metraipolis archive dc_126e9569f712, sha256 0f75fa152c79e5d5b9097cbb9597e5617fe99136599267f01e8d94d81bea0a00)

BibTeX

@misc{dc126e9569f712,
  title = {Kolmogorov structure function — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Kolmogorov_structure_function},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_126e9569f712; sha256 0f75fa152c79e5d5b9097cbb9597e5617fe99136599267f01e8d94d81bea0a00},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Kolmogorov_structure_function. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In 1973, Andrey Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let each datum be a finite binary string and a model be a finite set of binary strings. Consider model classes consisting of models of given maximal Kolmogorov complexity. The Kolmogorov structure function of an individual data string expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. The structure function determines all stochastic properties of the individual data string: for every constrained model class it determines the individual best-fitting model in the class irrespective of whether the true model is in the model class considered or not. In the classical case we talk about a set of data with a probability distribution, and the properties are those of the expectations. In contrast, here we deal with individual data strings and the properties of the individual string focused on. In this setting, a property holds with certainty rather than with high probability as in the classical case. The Kolmogorov structure function precisely quantifies the goodness-of-fit of an individual model with respect to individual data. The Kolmogorov structure function is used in the algorithmic information theory, also known as the theory of Kolmogorov complexity, for describing the structure of a string by use of models of increasing complexity.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «information theory»).
Fonte: Wikipedia in inglese, voce «Kolmogorov structure function» — https://en.wikipedia.org/wiki/Kolmogorov_structure_function
Wikidata Q5805968 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5805968
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Kolmogorov_structure_function?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1357101338, consultata il 2026-10-07T21:46:56.893Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c34886beef4e1a3c2ff332f8e0a6073159209990b226281b02513d6d26fee814