The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
type: Item
instance of: scholarly article
title: The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
zbMATH Open document ID: 1017.60002
author: George Davie
published in: The Annals of Probability
publication date: 2003-05-06T00:00:00Z
review text: 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.
reviewed by: Roman Frič
Mathematics Subject Classification ID: 60A05
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 1906024
zbMATH Keywords: effective Borel-Cantelli lemmas
zbMATH Keywords: probability law
zbMATH Keywords: Martin-Löf random sequence
zbMATH Keywords: Kolmogorov-Chejtin random sequence
zbMATH Keywords: Kolmogorov complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1015345756
OpenAlex ID: W1571949533
Wikidata QID: Q124817095
cites work: Q5538132
cites work: Q4023358
cites work: The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Algorithmic Information Theory
DOI: 10.1214/AOP/1015345756
description: scientific article; zbMATH DE number 1906024