| Title:
|
Kolmogorov complexity, pseudorandom generators and statistical models testing (English) |
| Author:
|
Šindelář, Jan |
| Author:
|
Boček, Pavel |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
38 |
| Issue:
|
6 |
| Year:
|
2002 |
| Pages:
|
[747]-759 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
An attempt to formalize heuristic concepts like strings (sequences resp.) “typical” for a probability measure is stated in the paper. Both generating and testing of such strings is considered. Kolmogorov complexity theory is used as a tool. Classes of strings “typical” for a given probability measure are introduced. It is shown that no pseudorandom generator can produce long strings from the classes. The time complexity of pseudorandom generators with oracles capable to recognize “typical” strings is shown to be at least exponential with respect to the length of the output. Tests proclaiming some strings “typical” are introduced. We show that the problem of testing strings to be “typical” is undecidable. As a consequence, the problem of correspondence between probability measures and data is undecidable too. If the Lebesgue measure is considered, then the conditional probability of failure of a test is shown to exceed a positive lower bound almost surely. (English) |
| Keyword:
|
Kolmogorov complexity |
| Keyword:
|
typical string |
| Keyword:
|
pseudorandom generator |
| MSC:
|
60A10 |
| MSC:
|
65C10 |
| MSC:
|
68Q30 |
| idZBL:
|
Zbl 1265.68083 |
| idMR:
|
MR1954395 |
| . |
| Date available:
|
2009-09-24T19:50:22Z |
| Last updated:
|
2015-03-26 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135500 |
| . |
| Reference:
|
[1] Calude C.: Theories of Computational Complexity.North–Holland, Amsterdam 1988 Zbl 0633.03034, MR 0919945 |
| Reference:
|
[2] Fine T. L.: Theories of Probability – an Examination of Foundations.Academic Press, New York 1973 Zbl 0275.60006, MR 0433529 |
| Reference:
|
[3] Kolmogorov A. N.: Three approaches to the quantitative definition of information.Problems Inform. Transmission 1 (1965), 1, 1–7 MR 0184801 |
| Reference:
|
[4] 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:
|
[5] Kramosil I., Šindelář J.: On pseudo-random sequences and their relation to a class of stochastical laws.Kybernetika 28 (1991), 6, 383–391 MR 1197721 |
| Reference:
|
[6] Li M., Vitayi P.: Introduction to Kolmogorov Complexity and its Applications.Springer, New York 1997 MR 1438307 |
| Reference:
|
[7] 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:
|
[8] Rogers H., Jr.: Theory of Recursive Functions and Effective Computability.McGraw–Hill, New York 1967 Zbl 0256.02015, MR 0224462 |
| Reference:
|
[9] Šindelář J., Boček P.: Kolmogorov complexity and probability measures.Kybernetika 38 (2002), 729–745 MR 1954394 |
| . |
