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

DOI10.1016/j.ic.2011.10.006zbMath1257.03067arXiv1007.5249OpenAlexW1593512589WikidataQ57349503 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é recurrenceBirkhoff's ergodic theoremMartin-Löf random real

Mathematics Subject Classification ID

Measure-preserving transformations (28D05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Ergodic theorems, spectral theory, Markov operators (37A30) Algorithmic randomness and dimension (03D32)

Related Items (19)

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

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

This page was built for publication: A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points