A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points

DOI10.1016/j.ic.2011.10.006zbMath1257.03067arXiv1007.5249WikidataQ57349503 ScholiaQ57349503MaRDI QIDQ418118

Alexander Shen, Laurent Bienvenu, Mathieu Hoyrup, Adam R. Day, Ilya Mezhirov

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.5249

zbMATH Keywords

Poincaré recurrence; Birkhoff's ergodic theorem; Martin-Löf random real

Mathematics Subject Classification ID

28D05: Measure-preserving transformations

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

37A30: Ergodic theorems, spectral theory, Markov operators

03D32: Algorithmic randomness and dimension

Related Items

Unnamed Item, Computable Measure Theory and Algorithmic Randomness, Computability of convergence rates in the ergodic theorem for Martin-Löf random points, UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS, A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE, Computing from projections of random points, USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS, ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS, Ergodic theorems and converses for PSPACE functions, On effective Birkhoff's ergodic theorem for computable actions of amenable groups, Algorithmic randomness and Fourier analysis, Martin-Löf randomness implies multiple recurrence in effectively closed sets, Nullifying randomness and genericity using symmetric difference, Algorithmic tests and randomness with respect to a class of measures, Randomness and uniform distribution modulo one, Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets, Schnorr randomness and the Lebesgue differentiation theorem, Denjoy, Demuth and density, Effective S-adic Symbolic Dynamical Systems

Cites Work

• Unnamed Item
• Unnamed Item
• An extension of van Lambalgen's theorem to infinitely many relative 1-random reals
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Algorithmic tests and randomness with respect to a class of measures
• Uniform test of algorithmic randomness over a general space
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Ergodic-Type Characterizations of Algorithmic Randomness
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Von Mises' definition of random sequences reconsidered
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей
• Exact Expressions for Some Randomness Tests