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 satisfies the ergodic recurrence property for a computable measure-preserving with respect to effectively closed sets, then it also satisfies Birkhoff's ergodic theorem for 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 classes. This answers a question of Hoyrup and Rojas.

**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**, 10.1007/s00224-010-9263-x**5.**Paul R. Halmos,*Lectures on ergodic theory*, Chelsea Publishing Co., New York, 1960. MR**0111817****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**, 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**, 10.1007/BFb0076224**8.**Cristóbal Rojas.

Algorithmic randomness and ergodic theory, May 2010.

5th Conference on Logic, Computability and Randomness.

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.