Kolmogorov's Structure Functions and Model Selection

Nikolai Vereshchagin, Paul Vitanyi

In 1974 Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider…