Kolmogorov complexity and probability measures

Jan Šindelář; Pavel Boček

Kybernetika (2002)

  • Volume: 38, Issue: 6, page [729]-745
  • ISSN: 0023-5954

Abstract

top
Classes of strings (infinite sequences resp.) with a specific flow of Kolmogorov complexity are introduced. Namely, lower bounds of Kolmogorov complexity are prescribed to strings (initial segments of infinite sequences resp.) of specified lengths. Dependence of probabilities of the classes on lower bounds of Kolmogorov complexity is the main theme of the paper. Conditions are found under which the probabilities of the classes of the strings are close to one. Similarly, conditions are derived under which the probabilities of the classes of the sequences equal one. It is shown that there are lower bounds of Kolmogorov complexity such that the studied classes of the strings are of probability close to one, classes of the sequences are of probability one, both with respect to almost all probability measures used in practice. A variant of theorem on infinite oscillations is derived.

How to cite

top

Šindelář, Jan, and Boček, Pavel. "Kolmogorov complexity and probability measures." Kybernetika 38.6 (2002): [729]-745. <http://eudml.org/doc/33615>.

@article{Šindelář2002,
abstract = {Classes of strings (infinite sequences resp.) with a specific flow of Kolmogorov complexity are introduced. Namely, lower bounds of Kolmogorov complexity are prescribed to strings (initial segments of infinite sequences resp.) of specified lengths. Dependence of probabilities of the classes on lower bounds of Kolmogorov complexity is the main theme of the paper. Conditions are found under which the probabilities of the classes of the strings are close to one. Similarly, conditions are derived under which the probabilities of the classes of the sequences equal one. It is shown that there are lower bounds of Kolmogorov complexity such that the studied classes of the strings are of probability close to one, classes of the sequences are of probability one, both with respect to almost all probability measures used in practice. A variant of theorem on infinite oscillations is derived.},
author = {Šindelář, Jan, Boček, Pavel},
journal = {Kybernetika},
keywords = {Kolmogorov complexity; probability measure; infinite oscillation; Kolmogorov complexity; probability measure; infinite oscillation},
language = {eng},
number = {6},
pages = {[729]-745},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Kolmogorov complexity and probability measures},
url = {http://eudml.org/doc/33615},
volume = {38},
year = {2002},
}

TY - JOUR
AU - Šindelář, Jan
AU - Boček, Pavel
TI - Kolmogorov complexity and probability measures
JO - Kybernetika
PY - 2002
PB - Institute of Information Theory and Automation AS CR
VL - 38
IS - 6
SP - [729]
EP - 745
AB - Classes of strings (infinite sequences resp.) with a specific flow of Kolmogorov complexity are introduced. Namely, lower bounds of Kolmogorov complexity are prescribed to strings (initial segments of infinite sequences resp.) of specified lengths. Dependence of probabilities of the classes on lower bounds of Kolmogorov complexity is the main theme of the paper. Conditions are found under which the probabilities of the classes of the strings are close to one. Similarly, conditions are derived under which the probabilities of the classes of the sequences equal one. It is shown that there are lower bounds of Kolmogorov complexity such that the studied classes of the strings are of probability close to one, classes of the sequences are of probability one, both with respect to almost all probability measures used in practice. A variant of theorem on infinite oscillations is derived.
LA - eng
KW - Kolmogorov complexity; probability measure; infinite oscillation; Kolmogorov complexity; probability measure; infinite oscillation
UR - http://eudml.org/doc/33615
ER -

References

top
  1. Calude C., Theories of Computational Complexity, North–Holland, Amsterdam – New York – Oxford – Tokyo 1988 Zbl0633.03034MR0919945
  2. Chaitin G. J., 10.1145/321356.321363, J. Assoc. Comput. Mach. 13 (1966), 547–569 (1966) Zbl0158.25301MR0210520DOI10.1145/321356.321363
  3. Fine T. L., Theories of Probability – an Examination of Foundations, Academic Press, New York – London 1973 Zbl0275.60006MR0433529
  4. Katseff H. P., 10.1016/S0019-9958(78)90062-1, Inform. and Control 38 (1978), 258–263 (1978) MR0509552DOI10.1016/S0019-9958(78)90062-1
  5. Kolmogorov A. N., Three approaches to the quantitative definition of information, Problems Inform. Transmission 1 (1965), 1, 1–7 (1965) MR0184801
  6. Kolmogorov A. N., Uspenskiǐ V. A., Algorithms and randomness (in Russian), Teor. Veryatnost. i Primenen. 32 (1987), 3, 425–455 (1987) MR0914935
  7. Kramosil I., Šindelář J., A note on the law of iterated logarithm from the viewpoint of Kolmogorov program complexity, Problems Control Inform. Theory 16 (1987), 6, 399–409 (1987) MR0930650
  8. Kramosil I., Šindelář J., On pseudo-random sequences and their relation to a class of stochastical laws, Kybernetika 28 (1992), 6, 383–391 (1992) Zbl0773.60006MR1197721
  9. Li M., Vitayi P., An Introduction to Kolmogorov Complexity and its Applications, Springer, New York 1997 MR1438307
  10. Martin–Löf P., 10.1016/S0019-9958(66)80018-9, Inform. and Control 9 (1966), 602–619 (1966) MR0223179DOI10.1016/S0019-9958(66)80018-9
  11. Martin–Löf P., 10.1007/BF00534110, Z. Wahrsch. Verw. Gebiete 19 (1971), 225–230 (1971) Zbl0212.23103MR0451322DOI10.1007/BF00534110
  12. Rogers H., Jr., Theory of Recursive Functions and Effective Computability, McGraw–Hill, New York 1967 Zbl0256.02015MR0224462
  13. Solomonoff R. J., 10.1016/S0019-9958(64)90223-2, Part I. Inform. and Control 7 (1964), 1–22 (1964) Zbl0259.68038MR0172744DOI10.1016/S0019-9958(64)90223-2
  14. Vovk V. G., The law of of the iterated logarithm for sequences that are random in the sense of Kolmogorov or chaotic (in Russian), Teor. Veroyatnost. i Primenen. 32 (1978), 3, 456–468 (1978) MR0914936

NotesEmbed ?

top

You must be logged in to post comments.