Kolmogorov complexity, pseudorandom generators and statistical models testing

Jan Šindelář; Pavel Boček

Kybernetika (2002)

  • Volume: 38, Issue: 6, page [747]-759
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Šindelář, Jan, and Boček, Pavel. "Kolmogorov complexity, pseudorandom generators and statistical models testing." Kybernetika 38.6 (2002): [747]-759. <http://eudml.org/doc/33616>.

@article{Šindelář2002,
abstract = {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.},
author = {Šindelář, Jan, Boček, Pavel},
journal = {Kybernetika},
keywords = {Kolmogorov complexity; typical string; pseudorandom generator; Kolmogorov complexity; typical string; pseudorandom generator},
language = {eng},
number = {6},
pages = {[747]-759},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Kolmogorov complexity, pseudorandom generators and statistical models testing},
url = {http://eudml.org/doc/33616},
volume = {38},
year = {2002},
}

TY - JOUR
AU - Šindelář, Jan
AU - Boček, Pavel
TI - Kolmogorov complexity, pseudorandom generators and statistical models testing
JO - Kybernetika
PY - 2002
PB - Institute of Information Theory and Automation AS CR
VL - 38
IS - 6
SP - [747]
EP - 759
AB - 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.
LA - eng
KW - Kolmogorov complexity; typical string; pseudorandom generator; Kolmogorov complexity; typical string; pseudorandom generator
UR - http://eudml.org/doc/33616
ER -

References

top
  1. Calude C., Theories of Computational Complexity, North–Holland, Amsterdam 1988 Zbl0633.03034MR0919945
  2. Fine T. L., Theories of Probability – an Examination of Foundations, Academic Press, New York 1973 Zbl0275.60006MR0433529
  3. Kolmogorov A. N., Three approaches to the quantitative definition of information, Problems Inform. Transmission 1 (1965), 1, 1–7 (1965) MR0184801
  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 (1987) MR0930650
  5. Kramosil I., Šindelář J., On pseudo-random sequences and their relation to a class of stochastical laws, Kybernetika 28 (1991), 6, 383–391 (1991) MR1197721
  6. Li M., Vitayi P., Introduction to Kolmogorov Complexity and its Applications, Springer, New York 1997 MR1438307
  7. 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
  8. Rogers H., Jr., Theory of Recursive Functions and Effective Computability, McGraw–Hill, New York 1967 Zbl0256.02015MR0224462
  9. Šindelář J., Boček P., Kolmogorov complexity and probability measures, Kybernetika 38 (2002), 729–745 MR1954394

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.