Geodesic
Kolmogorov complexity and probability measures
Kybernetika, Tome 38 (2002) no. 6, p. [729].

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

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