Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets
HTML articles powered by AMS MathViewer
- by Johanna N. Y. Franklin, Noam Greenberg, Joseph S. Miller and Keng Meng Ng PDF
- Proc. Amer. Math. Soc. 140 (2012), 3623-3628 Request permission
Abstract:
We show that if a point in a computable probability space $X$ satisfies the ergodic recurrence property for a computable measure-preserving $T\colon X\to X$ with respect to effectively closed sets, then it also satisfies Birkhoff’s ergodic theorem for $T$ with respect to effectively closed sets. As a corollary, every Martin-Löf random sequence in the Cantor space satisfies Birkhoff’s ergodic theorem for the shift operator with respect to $\Pi ^0_1$ classes. This answers a question of Hoyrup and Rojas.References
- Laurent Bienvenu, Adam Day, Mathieu Hoyrup, Ilya Mezhirov, and Alexander Shen. A constructive version of Birkhoff’s ergodic theorem for Martin-Löf random points. To appear in Information and Computation.
- Laurent Bienvenu, Adam Day, Ilya Mezhirov, and Alexander Shen. Ergodic-type characterizations of algorithmic randomness. In 6th Conference on Computability in Europe, LNCS 6158, pp. 49–58, 2010.
- Laurent Bienvenu, Mathieu Hoyrup, and Alexander Shen. Personal communication.
- Peter Gács, Mathieu Hoyrup, and Cristóbal Rojas, Randomness on computable probability spaces—a dynamical point of view, Theory Comput. Syst. 48 (2011), no. 3, 465–485. MR 2770804, DOI 10.1007/s00224-010-9263-x
- Paul R. Halmos, Lectures on ergodic theory, Chelsea Publishing Co., New York, 1960. MR 0111817
- Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput. 207 (2009), no. 7, 830–847. MR 2519075, DOI 10.1016/j.ic.2008.12.009
- Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
- Cristóbal Rojas. Algorithmic randomness and ergodic theory, May 2010. 5th Conference on Logic, Computability and Randomness.
Additional Information
- Johanna N. Y. Franklin
- Affiliation: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hanover, New Hampshire 03755-3551
- Email: johannaf@gauss.dartmouth.edu
- Noam Greenberg
- Affiliation: School of Mathematics, Statistics, and Operations Research, Victoria University of Wellington, P.O. Box 600, Wellington, 6140 New Zealand
- MR Author ID: 757288
- ORCID: 0000-0003-2917-3848
- Email: greenberg@mcs.vuw.ac.nz
- Joseph S. Miller
- Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706-1388
- MR Author ID: 735102
- Email: jmiller@math.wisc.edu
- Keng Meng Ng
- Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706-1388
- MR Author ID: 833062
- Email: selwynng@math.wisc.edu
- Received by editor(s): July 20, 2010
- Received by editor(s) in revised form: April 5, 2011, and April 8, 2011
- Published electronically: February 20, 2012
- Additional Notes: The second author was partially supported by the Marsden Grant of New Zealand
The third author was supported by the National Science Foundation under grants DMS-0945187 and DMS-0946325, the latter being part of a Focused Research Group in Algorithmic Randomness. - Communicated by: Julia Knight
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 140 (2012), 3623-3628
- MSC (2010): Primary 03D22; Secondary 28D05, 37A30
- DOI: https://doi.org/10.1090/S0002-9939-2012-11179-7
- MathSciNet review: 2929030