×

A constructive version of Birkhoff’s ergodic theorem for Martin-Löf random points. (English) Zbl 1257.03067

The authors prove a constructive version of Birkhoff’s ergodic theorem for Martin-Löf random reals and effectively open sets. From the proof one can extract a new simple proof of the effective ergodic theorem. The main result was independently obtained by J. N. Y Franklin, N. Greenberg, J. S. Miller and K. M. Ng in [“Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets”, Proc. Am. Math. Soc. 140, No. 10, 3623–3628 (2012; doi:10.1090/S0002-9939-2012-11179-7)].

MSC:

03D32 Algorithmic randomness and dimension
28D05 Measure-preserving transformations
37A30 Ergodic theorems, spectral theory, Markov operators
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Bienvenu, Laurent; Day, Adam; Mezhirov, Ilya; Shen, Alexander, Ergodic-type characterizations of algorithmic randomness, (Computability in Europe (CIE 2010). Computability in Europe (CIE 2010), Lecture Notes in Comput. Sci., vol. 6158 (2010), Springer), 49-58 · Zbl 1286.03138
[2] Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen, Algorithmic tests and randomness with respect to a class of measures, in press, available at http://arxiv.org/abs/1103.1529; Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen, Algorithmic tests and randomness with respect to a class of measures, in press, available at http://arxiv.org/abs/1103.1529 · Zbl 1294.03032
[3] Johanna N.Y. Franklin, Noam Greenberg, Joseph S. Miller, Keng Meng Ng, Martin-Löf random points satisfy Birkhoffʼs ergodic theorem for effectively closed sets, Proc. Amer. Math. Soc., in press.; Johanna N.Y. Franklin, Noam Greenberg, Joseph S. Miller, Keng Meng Ng, Martin-Löf random points satisfy Birkhoffʼs ergodic theorem for effectively closed sets, Proc. Amer. Math. Soc., in press.
[4] Gács, Peter, Exact expressions for some randomness tests, Z. Math. Logik Grundlagen Math., 26, 385-394 (1980) · Zbl 0464.60004
[5] Gács, Peter, Uniform test of algorithmic randomness over a general space, Theoret. Comput. Sci., 341, 91-137 (2005) · Zbl 1077.68038
[6] Hoyrup, Mathieu; Rojas, Cristobal, An application of Martin-Löf randomness to effective probability theory, (Computability in Europe (CIE 2009). Computability in Europe (CIE 2009), Lecture Notes in Comput. Sci., vol. 5635 (2009)), 260-269 · Zbl 1268.03055
[7] Hoyrup, Mathieu; Rojas, Cristóbal, Applications of effective probability theory to Martin-Löf randomness, (International Colloquium on Automata, Languages and Programming (ICALP 2009). International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Comput. Sci., vol. 5555 (2009), Springer), 549-561 · Zbl 1248.03066
[8] Hoyrup, Mathieu; Rojas, Cristóbal, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput., 207, 7, 2207-2222 (2009) · Zbl 1167.68023
[9] Kučera, Antonin, Measure, \( \Pi_1^0\) classes, and complete extensions of PA, Lecture Notes in Math., 1141, 245-259 (1985) · Zbl 0622.03031
[10] Kenshi Miyabe, An extension of van Lambalgenʼs theorem to infinitely many relative 1-random reals, Notre Dame J. Formal Logic, in press.; Kenshi Miyabe, An extension of van Lambalgenʼs theorem to infinitely many relative 1-random reals, Notre Dame J. Formal Logic, in press. · Zbl 1208.03045
[11] Nandakumar, Satyadev, An effective ergodic theorem and some applications, (STOCʼ08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), ACM: ACM New York, NY, USA), 39-44 · Zbl 1231.37064
[12] Shiryaev, Albert, Probability (1996), Springer
[13] Michiel van Lambalgen, Random sequences, PhD dissertation, University of Amsterdam, Amsterdam, 1987.; Michiel van Lambalgen, Random sequences, PhD dissertation, University of Amsterdam, Amsterdam, 1987. · Zbl 0628.60001
[14] Vyugin, Vladimir, Effective convergence in probability and an ergodic theorem for individual random sequences, Theory Probab. Appl., 42, 1, 39-50 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.