A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
From MaRDI portal
Publication:418118
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
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