Geodesic
Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
Teoriâ veroâtnostej i ee primeneniâ, Tome 68 (2023) no. 4, pp. 719-750 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The definition of descriptional complexity of finite objects suggested by Kolmogorov and other authors in the mid-1960s is now well known. In addition, Kolmogorov pointed out some approaches to a more fine-grained classification of finite objects, such as the resource-bounded complexity (1965), structure function (1974), and the notion of $(\alpha,\beta)$-stochasticity (1981). Later it turned out that these approaches are essentially equivalent in that they define the same curve in different coordinates. In this survey, we try to follow the development of these ideas of Kolmogorov as well as similar ideas suggested independently by other authors.
Keywords: Kolmogorov complexity, algorithmic statistics, resource-bounded complexity, Kolmogorov's structure function, $(\alpha,\beta)$-stochasticity. 
@article{TVP_2023_68_4_a3,
     author = {N. K. Vereshchagin and A. L. Semenov and A. Kh. Shen'},
     title = {Kolmogorov{\textquoteright}s last discovery? {(Kolmogorov} and algorithmic statistics)},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {719--750},
     year = {2023},
     volume = {68},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/}
}
TY  - JOUR
AU  - N. K. Vereshchagin
AU  - A. L. Semenov
AU  - A. Kh. Shen'
TI  - Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2023
SP  - 719
EP  - 750
VL  - 68
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/
LA  - ru
ID  - TVP_2023_68_4_a3
ER  - 
%0 Journal Article
%A N. K. Vereshchagin
%A A. L. Semenov
%A A. Kh. Shen'
%T Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2023
%P 719-750
%V 68
%N 4
%U http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/
%G ru
%F TVP_2023_68_4_a3
N. K. Vereshchagin; A. L. Semenov; A. Kh. Shen'. Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics). Teoriâ veroâtnostej i ee primeneniâ, Tome 68 (2023) no. 4, pp. 719-750. http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/

[1] R. J. Solomonoff, A preliminary report on a general theory of inductive inference, Rep. V-131, Contract AF 49(638)-376, Zator Co., Cambridge, MA, 1960, iii+26 pp. http://raysolomonoff.com/publications/rayfeb60.pdf

[2] A. N. Kolmogorov, “O tablitsakh sluchainykh chisel”, Izbrannye trudy, v. 3, Teoriya informatsii i teoriya algoritmov, Nauka, M., 1987, 270–274 ; A. N. Kolmogorov, “On tables of random numbers”, Sankhyā Ser. A, 25:4 (1963), 369–376 ; Theoret. Comput. Sci., 207:2 (1998), 387–395 https://www.jstor.org/stable/25049284 | MR | Zbl | MR | Zbl | DOI | MR | Zbl

[3] R. J. Solomonoff, “A formal theory of inductive inference. Part I”, Information and Control, 7:1 (1964), 1–22 | DOI | MR | Zbl

[4] R. J. Solomonoff, “A formal theory of inductive inference. Part II”, Information and Control, 7:2 (1964), 224–254 | DOI | MR | Zbl

[5] A. N. Kolmogorov, “Ponyatie ‘informatsiya’ i osnovy teorii veroyatnostei”, stenogr. dokl. v In-te filosofii AN SSSR, M., 05.04.1965 g. i otvety na vopr., prislan. vo vremya dokl., Kolmogorov i kibernetika, Voprosy istorii informatiki, 2, eds. D. A. Pospelov, Ya. I. Fet, IVMiMG SO RAN, Novosibirsk, 2001, 118–142 https://archive.org/details/kolmogorov-1965talk

[6] A. N. Kolmogorov, “Three approaches to the quantitative definition of information”, Internat. J. Comput. Math., 2:1-4 (1968), 157–168 | DOI | MR | MR | Zbl | Zbl

[7] A. N. Kolmogorov, “Neskolko teorem ob algoritmicheskoi entropii i algoritmicheskom kolichestve informatsii”, v st. “Zasedaniya Moskovskogo matematicheskogo obschestva”, UMN, 23:2(140) (1968), 201

[8] C. S. Wallace, D. M. Boulton, “An information measure for classification”, Comput. J., 11:2 (1968), 185–194 | DOI | Zbl

[9] A. Kolmogoroff, “Logical basis for information theory and probability theory”, Problems Inform. Transmission, 5:3 (1969), 1–4 ; IEEE Trans. Inform. Theory, 14:5 (1968), 662–664 | DOI | MR | MR | Zbl | Zbl

[10] A. N. Kolmogorov, “Combinatorial foundations of information theory and the calculus of probabilities”, Russian Math. Surveys, 38:4 (1983), 29–40 ; 1970, 20 с. https://archive.org/details/kolmogorov83-manuscript | DOI | MR | Zbl

[11] A. N. Kolmogorov, “Slozhnost zadaniya i slozhnost postroeniya matematicheskikh ob'ektov”, v st.: “Zasedaniya Moskovskogo matematicheskogo obschestva”, UMN, 27:2(164) (1972), 159

[12] A. N. Kolmogorov, “Slozhnost algoritmov i ob'ektivnoe opredelenie sluchainosti”, v st.: “Zasedaniya Moskovskogo matematicheskogo obschestva”, UMN, 29:4(178) (1974), 155

[13] G. J. Chaitin, “Algorithmic information theory”, IBM J. Res. Develop., 21:4 (1977), 350–359 | DOI | MR | Zbl

[14] J. Rissanen, “Modeling by shortest data description”, Automatica J. IFAC, 14:5 (1978), 465–471 ; https://msol.people.uic.edu/ECE531/papers/Modeling By Shortest Data Description.pdf | DOI | Zbl

[15] L. M. Adleman, Time, space and randomness, Rep. MIT/LCS/TM-131, MIT LCS, Cambridge, MA, 1979, 19 pp. https://people.cs.rutgers.edu/~allender/papers/adleman.time.space.randomness.pdf

[16] Probability theory and mathematical statistics, Proceedings of the fourth USSR–Japan symposium (Tbilisi, 1982), Lecture Notes in Math., 1021, eds. K. Itô, J. V. Prokhorov, Springer-Verlag, Berlin, 1983, viii+746 pp. | DOI | MR | Zbl

[17] A. N. Kolmogorov, “On logical foundations of probability theory”, Probability theory and mathematical statistics, Proceedings of the fourth USSR–Japan symposium (Tbilisi, 1982), Lecture Notes in Math., 1021, eds. K. Itô, J. V. Prokhorov, Springer-Verlag, Berlin, 1983, 1–5 | DOI | MR | Zbl

[18] P. Gács, “On the relation between descriptional complexity and algorithmic probability”, Theoret. Comput. Sci., 22:1-2 (1983), 71–93 | DOI | MR | Zbl

[19] M. Sipser, “A complexity theoretic approach to randomness”, STOC {'}83: Proceedings of the 15th annual ACM symposium on theory of computing (Boston, MA, 1983), Association for Computing Machinery (ACM), New York, 1983, 330–335 | DOI | MR | Zbl

[20] A. Kh. Shen', “The concept of $(\alpha,\beta)$-stochasticity in the Kolmogorov sense, and its properties”, Soviet Math. Dokl., 28 (1983), 295–299 | MR | Zbl

[21] T. M. Cover, “Kolmogorov complexity, data compression, and inference”, The impact of processing techniques on communications, ed. J. K. Skwirzynski, Martinus Nijhoff Publishers, Dordrecht–Boston–Lankaster, 1985, 23–33 https://isl.stanford.edu/~cover/papers/paper65.pdf

[22] V. V. V'yugin, “On nonstochastic objects”, Problems Inform. Transmission, 21:2 (1985), 77–83 | MR | Zbl

[23] L. Longpré, Resource bounded Kolmogorov complexity, a link between computational complexity and information theory, Ph.D. thesis, TR 86-776, Dep. of Comput. Sci., Cornell Univ., Ithaca, NY, 1986, 101 pp. https://ecommons.cornell.edu/handle/1813/6616

[24] “Welcoming speech by Andrei Nikolaevich Kolmogorov to the participants of the First World congress of the Bernoulli Society”, In: A. N. Shiryaev, A. A. Novikov, E. L. Presman, “The First World congress of the Bernoulli society of mathematical statistics and probability”, Theory Probab. Appl., 32:2 (1987), 200 | DOI

[25] A. N. Kolmogorov, V. A. Uspenskii, “Algorithms and randomness”, Theory Probab. Appl., 32:3 (1987), 389–412 | DOI | MR | Zbl

[26] E. A. Asarin, “On some properties of finite objects random in an algorithmic sense”, Soviet Math. Dokl., 36:1 (1988), 109–112 | MR | Zbl

[27] E. A. Asarin, “Some properties of Kolmogorov $\Delta$-random finite sequences”, Theory Probab. Appl., 32:3 (1987), 507–508 | DOI | MR | Zbl

[28] V. V. Vjugin, “On the defect of randomness of a finite object with respect to measures with given complexity bounds”, Theory Probab. Appl., 32:3 (1987), 508–512 | DOI | MR | Zbl

[29] M. Koppel, “Complexity, depth, and sophistication”, Complex systems, 1:6 (1987), 1087–1091 https://www.complex-systems.com/abstracts/v01_i06_a04/ | MR | Zbl

[30] C. H. Bennett, “Logical depth and physical complexity”, The universal Turing machine — a half-century survey, Oxford Sci. Publ., ed. R. Herken, Oxford Univ. Press, New York, 1988, 227–257 | MR | Zbl

[31] M. Koppel, “Structure”, The universal Turing machine — a half-century survey, Oxford Sci. Publ., ed. R. Herken, Oxford Univ. Press, New York, 1988, 435–452 | MR | Zbl

[32] T. M. Cover, P. Gacs, R. M. Gray, “Kolmogorov's contributions to information theory and algorithmic complexity”, Ann. Probab., 17:3 (1989), 840–865 | DOI | MR | Zbl

[33] M. Koppel, H. Atlan, “An almost machine-independent theory of program-length complexity, sophistication, and induction”, Inform. Sci., 56:1-3 (1991), 23–33 | DOI | MR | Zbl

[34] T. M. Cover, J. A. Thomas, Elements of information theory, Wiley Ser. Telecom., Wiley-Intersci. Publ., John Wiley Sons, Inc., New York, 1991, xxiv+542 pp. ; 2nd ed., 2006, xxiv+748 pp. | DOI | MR | Zbl | DOI | MR | Zbl

[35] Ming Li, P. M. B. Vitányi, “Inductive reasoning and Kolmogorov complexity”, J. Comput. System Sci., 44:2 (1992), 343–384 ; preliminary version in: Proceedings. Structure in complexity theory: fourth annual conference (Eugene, OR, 1989), IEEE, 1989, 165–185 | DOI | MR | Zbl | DOI

[36] L. Longpré, S. Mocas, “Symmetry of information and one-way functions”, Inform. Process. Lett., 46:2 (1993), 95–100 | DOI | MR | Zbl

[37] J. Rissanen, “Hypotheses selection and testing by the MDL principle”, Comput. J., 42:4 (1999), 260–269 https://ieeexplore.ieee.org/document/8138703 | Zbl

[38] A. Shen, “Discussion on Kolmogorov complexity and statistical analysis”, Comput. J., 42:4 (1999), 340–342 | DOI | Zbl

[39] V. V. V'yugin, “Algorithmic complexity and stochastic properties of finite binary sequences”, Comput. J., 42:4 (1999), 294–317 | DOI | Zbl

[40] C. S. Wallace, D. L. Dowe, “Minimum message length and Kolmogorov complexity”, Comput. J., 42:4 (1999), 270–283 | DOI | Zbl

[41] Qiong Gao, Ming Li, P. Vitányi, “Applying MDL to learn best model granularity”, Artificial Intelligence, 121:1-2 (2000), 1–29 | DOI | MR | Zbl

[42] P. M. B. Vitányi, Ming Li, “Minimum description length induction, Bayesianism, and Kolmogorov complexity”, IEEE Trans. Inform. Theory, 46:2 (2000), 446–464 | DOI | MR | Zbl

[43] P. Gács, J. T. Tromp, P. M. B. Vitányi, “Algorithmic statistics”, IEEE Trans. Inform. Theory, 47:6 (2001), 2443–2463 | DOI | MR | Zbl

[44] G. Shafer, V. Vovk, Probability and finance. It's only a game!, Wiley Ser. Probab. Stat. Financial Eng. Sect., Wiley-Intersci. John Wiley Sons, Inc., New York, 2001, xii+478 pp. | DOI | MR | Zbl

[45] N. K. Vereshchagin, P. M. B. Vitányi, “Kolmogorov's structure functions and model selection”, IEEE Trans. Inform. Theory, 50:12 (2004), 3265–3290 ; (2004 (v1 – 2002)), 25 pp., arXiv: cs/0204037 | DOI | MR | Zbl

[46] P. Grunwald, A tutorial introduction to the minimum description length principle, 2004, 80 pp., arXiv: math/0406077

[47] L. Antunes, L. Fortnow, D. van Melkebeek, N. V. Vinodchandran, “Computational depth: concept and applications”, Theoret. Comput. Sci., 354:3 (2006), 391–404 | DOI | MR | Zbl

[48] P. M. Vitányi, “Meaningful information”, IEEE Trans. Inform. Theory, 52:10 (2006), 4617–4626 ; (2006 (v1 – 2001)), 12 pp., arXiv: cs/0111053v3 | DOI | MR | Zbl

[49] L. Antunes, L. Fortnow, “Sophistication revisited”, Theory Comput. Syst., 45:1 (2009), 150–161 | DOI | MR | Zbl

[50] A. Nies, Computability and randomness, Oxford Logic Guides, 51, Oxford Univ. Press, Oxford, 2009, xvi+433 pp. https://global.oup.com/academic/product/computability-and-randomness-9780199652600 | MR | Zbl

[51] R. G. Downey, D. R. Hirschfeldt, Algorithmic randomness and complexity, Theory Appl. Comput., Springer, New York, 2010, xxviii+855 pp. | DOI | MR | Zbl

[52] B. Bauwens, Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity, Ph.D. thesis, Univ. of Ghent, Ghent, 2010, xviii+142 pp. https://biblio.ugent.be/publication/1107852

[53] N. K. Vereschagin, V. A. Uspenskii, A. Shen, Kolmogorovskaya slozhnost i algoritmicheskaya sluchainost, MTsNMO, M., 2013, 576 pp. ; A. Shen, V. A. Uspensky, N. Vereshchagin, Kolmogorov complexity and algorithmic randomness, Math. Surveys Monogr., 220, Amer. Math. Soc., Providence, RI, 2017, xviii+511 с. ; https://hal-lirmm.ccsd.cnrs.fr/lirmm-00786255/documenthttps://hal-lirmm.ccsd.cnrs.fr/lirmm-01803620v1/document | DOI | MR | Zbl

[54] N. Vereshchagin, A. Shen, “Algorithmic statistics revisited”, Measures of complexity. Festschrift for Alexey Chervonenkis, eds. V. Vovk, H. Papadopoulos, A. Gammerman, Springer, Cham, 2015, 235–252 | DOI | MR | Zbl

[55] N. Vereshchagin, A. Shen, “Algorithmic statistics: forty years later”, Computability and complexity, Essays dedicated to R. G. Downey on the occasion of his 60th birthday, Lecture Notes in Comput. Sci., 10010, eds. A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, F. Rosamond, Springer, Cham, 2016, 669–737 ; 2017 (v1 – 2016), 102 pp., arXiv: 1607.08077 | DOI | MR | Zbl

[56] L. Antunes, B. Bauwens, A. Souto, A. Teixeira, “Sophistication vs logical depth”, Theory Comput. Syst., 60:2 (2017), 280–298 ; (2017 (v1 – 2013)), 9 pp., arXiv: 1304.8046 | DOI | MR | Zbl

[57] Materialy zasedanii “Kolmogorovskogo seminara” https://www.youtube.com/channel/UC20xHyxD6FqItj2N6y3eSZg