The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity (Q1872229): Difference between revisions

Ideas and tools from Kolmogorov complexity [\textit{M. Li} and \textit{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.