Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

   

 

Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets


Authors: Johanna N. Y. Franklin, Noam Greenberg, Joseph S. Miller and Keng Meng Ng
Journal: Proc. Amer. Math. Soc. 140 (2012), 3623-3628
MSC (2010): Primary 03D22; Secondary 28D05, 37A30
Published electronically: February 20, 2012
MathSciNet review: 2929030
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. 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.
  • 3. Laurent Bienvenu, Mathieu Hoyrup, and Alexander Shen.
    Personal communication.
  • 4. 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 (2012f:03070), 10.1007/s00224-010-9263-x
  • 5. Paul R. Halmos, Lectures on ergodic theory, Chelsea Publishing Co., New York, 1960. MR 0111817 (22 #2677)
  • 6. 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 (2011b:03066), 10.1016/j.ic.2008.12.009
  • 7. Antonín Kučera, Measure, Π⁰₁-classes and complete extensions of 𝑃𝐴, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784 (87e:03102), 10.1007/BFb0076224
  • 8. Cristóbal Rojas.
    Algorithmic randomness and ergodic theory, May 2010.
    5th Conference on Logic, Computability and Randomness.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D22, 28D05, 37A30

Retrieve articles in all journals with MSC (2010): 03D22, 28D05, 37A30


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
Email: greenberg@mcs.vuw.ac.nz

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706-1388
Email: jmiller@math.wisc.edu

Keng Meng Ng
Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706-1388
Email: selwynng@math.wisc.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-2012-11179-7
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
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.