page_title: Kolmogorov structure function
section_title: Kolmogorov's definition
hierarchical_section_title: Kolmogorov structure function / Kolmogorov's definition
caption_attribution_description: taken at the 1973 Soviet Information Theory Symposium (may not be the exact title) held in Tallinn, Estonian SSR. Kolmogorov delivers his talk. A.M. Yaglom is also on the picture.
context_page_description: In 1973 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.
context_section_description: The structure function was originally proposed by Kolmogorov in 1973 at a Soviet Information Theory symposium in Tallinn, but these results were not published p. 182. But the results were announced in in 1974, the only written record by Kolmogorov himself. One of his last scientific statements is (translated from the original Russian by L.A. Levin):
  To each constructive object corresponds a function  of a natural number k—the log of minimal cardinality of x-containing sets that allow definitions of complexity at most k. If the element x itself allows a simple definition, then the function  drops to 0 even for small k. Lacking such definition, the element is "random" in a negative sense. But it is positively "probabilistically random" only when function  having taken the value  at a relatively small , then changes approximately as .
  — Kolmogorov, announcement cited above
caption: Kolmogorov (left) talks on the structure function (see drawing on the blackboard)  in  (Tallinn, 1973).
exif: {"Image ImageWidth": "1398", "Image ImageLength": "942", "Image BitsPerSample": "[8, 8, 8]", "Image PhotometricInterpretation": "2", "Image Orientation": "Horizontal (normal)", "Image SamplesPerPixel": "3", "Image XResolution": "300", "Image YResolution": "300", "Image ResolutionUnit": "Pixels/Inch", "Image Software": "Adobe Photoshop CC 2015 (Macintosh)", "Image DateTime": "2016:02:03 15:05:08", "Image ExifOffset": "236", "Thumbnail Compression": "JPEG (old-style)", "Thumbnail XResolution": "72", "Thumbnail YResolution": "72", "Thumbnail ResolutionUnit": "Pixels/Inch", "Thumbnail JPEGInterchangeFormat": "386", "Thumbnail JPEGInterchangeFormatLength": "0", "EXIF ExifVersion": "0221", "EXIF ColorSpace": "Uncalibrated", "EXIF ExifImageWidth": "1374", "EXIF ExifImageLength": "910"}