Algorithmic information theory and martingales

2009/06/15 by Laurent Bienvenu, Alexander Shen, Bienvenu, Laurent +1
Computer Science · Mathematics · #60A99 #68Q30 #Algorithms and Data Compression #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #History and Overview (math.HO)

paper · pdf · doi:10.48550/arxiv.0906.2614

openalex publication_date 2009/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The notion of an individual random sequence goes back to von Mises. We describe the evolution of this notion, especially the use of martingales (suggested by Ville), and the development of algorithmic information theory in 1960s and 1970s (Solomonov, Kolmogorov, Martin-Lof, Levin, Chaitin, Schnorr and others). We conclude with some remarks about the use of the algorithmic information theory in the foundations of probability theory.

Related

• Algorithmic information theory
• Randomness Conservation Inequalities; Information and Independence in Mathematical Theories
• Algorithmic statistics: forty years later
• Kolmogorov's Algorithmic Mutual Information Is Equivalent to Bayes' Law
• An operational characterization of the notion of probability by\n algorithmic randomness and its applications