| Title:
|
Kolmogorov complexity and probability measures (English) |
| Author:
|
Šindelář, Jan |
| Author:
|
Boček, Pavel |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
38 |
| Issue:
|
6 |
| Year:
|
2002 |
| Pages:
|
[729]-745 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
Kolmogorov complexity |
| Keyword:
|
probability measure |
| Keyword:
|
infinite oscillation |
| MSC:
|
60A10 |
| MSC:
|
68Q30 |
| idZBL:
|
Zbl 1265.68082 |
| idMR:
|
MR1954394 |
| . |
| Date available:
|
2009-09-24T19:50:14Z |
| Last updated:
|
2015-03-26 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135499 |
| . |
| Reference:
|
[1] Calude C.: Theories of Computational Complexity.North–Holland, Amsterdam – New York – Oxford – Tokyo 1988 Zbl 0633.03034, MR 0919945 |
| Reference:
|
[2] Chaitin G. J.: On the length of programs for computing finite binary sequences.J. Assoc. Comput. Mach. 13 (1966), 547–569 Zbl 0158.25301, MR 0210520, 10.1145/321356.321363 |
| Reference:
|
[3] Fine T. L.: Theories of Probability – an Examination of Foundations.Academic Press, New York – London 1973 Zbl 0275.60006, MR 0433529 |
| Reference:
|
[4] Katseff H. P.: Complexity dips in infinite binary sequences.Inform. and Control 38 (1978), 258–263 MR 0509552, 10.1016/S0019-9958(78)90062-1 |
| Reference:
|
[5] Kolmogorov A. N.: Three approaches to the quantitative definition of information.Problems Inform. Transmission 1 (1965), 1, 1–7 MR 0184801 |
| Reference:
|
[6] Kolmogorov A. N., Uspenskiǐ V. A.: Algorithms and randomness (in Russian).Teor. Veryatnost. i Primenen. 32 (1987), 3, 425–455 MR 0914935 |
| Reference:
|
[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 MR 0930650 |
| Reference:
|
[8] Kramosil I., Šindelář J.: On pseudo-random sequences and their relation to a class of stochastical laws.Kybernetika 28 (1992), 6, 383–391 Zbl 0773.60006, MR 1197721 |
| Reference:
|
[9] Li M., Vitayi P.: An Introduction to Kolmogorov Complexity and its Applications.Springer, New York 1997 MR 1438307 |
| Reference:
|
[10] Martin–Löf P.: The definition of random sequences.Inform. and Control 9 (1966), 602–619 MR 0223179, 10.1016/S0019-9958(66)80018-9 |
| Reference:
|
[11] Martin–Löf P.: Complexity oscillations in infinite binary sequences.Z. Wahrsch. Verw. Gebiete 19 (1971), 225–230 Zbl 0212.23103, MR 0451322, 10.1007/BF00534110 |
| Reference:
|
[12] Rogers H., Jr.: Theory of Recursive Functions and Effective Computability.McGraw–Hill, New York 1967 Zbl 0256.02015, MR 0224462 |
| Reference:
|
[13] Solomonoff R. J.: A formal theory of inductive inference.Part I. Inform. and Control 7 (1964), 1–22 Zbl 0259.68038, MR 0172744, 10.1016/S0019-9958(64)90223-2 |
| Reference:
|
[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 MR 0914936 |
| . |
