The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity. (English) Zbl 1017.60002

Ideas and tools from Kolmogorov complexity [M. Li and P. Vitányi, “An introduction to Kolmogorov complexity and its applications” (1993; Zbl 0805.68063)] are used to formulate effective versions of the Borel-Cantelli lemmas, the strong law of large numbers, and the law of iterated logarithm. The standard formulation of probability theorem “\(\mathbb P\) holds with probability one” is replaced by “\(\mathbb P\) holds for each (Martin-Löf) random infinite sequence” for effective predicates. Sure, such results give sharper insight into probabilistic phenomena.


60A05 Axioms; other general questions in probability
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI


[1] Feller, W. (1968). An Introduction to Probability Theory and Its Applications 1, 3rd ed. Wiley, New York. · Zbl 0155.23101
[2] Li, M. and Vitányi, P. (1993). An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York. · Zbl 0805.68063
[3] Vovk, V. G. (1987). The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences. Theory Probab. Appl. 32 413-425. · Zbl 0645.60006
[4] Chaitin, G. J. (1975). A theory of program size formally identical to information theory. J. Assoc. Comput. Mach. 22 329-340. · Zbl 0309.68045
[5] Chaitin, G. J. (1987). Algorithmic Information Theory. Cambridge Univ. Press. · Zbl 0655.68003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.