Geodesic
Kolmogorov complexity, pseudorandom generators and statistical models testing
Kybernetika, Tome 38 (2002) no. 6, p. [747].

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 60A10, 65C10, 68Q30
Keywords: Kolmogorov complexity; typical string; pseudorandom generator 
@article{KYB_2002__38_6_a5,
     author = {\v{S}indel\'a\v{r}, Jan and Bo\v{c}ek, Pavel},
     title = {Kolmogorov complexity, pseudorandom generators and statistical models testing},
     journal = {Kybernetika},
     pages = {[747]},
     publisher = {mathdoc},
     volume = {38},
     number = {6},
     year = {2002},
     mrnumber = {1954395},
     zbl = {1265.68083},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2002__38_6_a5/}
}
TY  - JOUR
AU  - Šindelář, Jan
AU  - Boček, Pavel
TI  - Kolmogorov complexity, pseudorandom generators and statistical models testing
JO  - Kybernetika
PY  - 2002
SP  - [747]
VL  - 38
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2002__38_6_a5/
LA  - en
ID  - KYB_2002__38_6_a5
ER  - 
%0 Journal Article
%A Šindelář, Jan
%A Boček, Pavel
%T Kolmogorov complexity, pseudorandom generators and statistical models testing
%J Kybernetika
%D 2002
%P [747]
%V 38
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2002__38_6_a5/
%G en
%F KYB_2002__38_6_a5
Šindelář, Jan; Boček, Pavel. Kolmogorov complexity, pseudorandom generators and statistical models testing. Kybernetika, Tome 38 (2002) no. 6, p. [747]. http://geodesic.mathdoc.fr/item/KYB_2002__38_6_a5/