A constructive version of Birkhoff's ergodic theorem for Martin-Lof random points

Laurent Bienvenu (1) , Adam Day (2) , Mathieu Hoyrup (3) , Ilya Mezhirov (4) , Alexander Shen (5)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 Miller Institute for Basic Research in Science
3 CARTE - Theoretical adverse computations, and safety
4 TU Kaiserslautern - Technical University of Kaiserslautern
5 ESCAPE - Systèmes complexes, automates et pavages

A theorem of Kucera states that given a Martin-Löf random infinite binary sequence {\omega} and an effectively open set A of measure less than 1, some tail of {\omega} is not in A. We first prove several results in the same spirit and generalize them via an effective version of a weak form of Birkhoff's ergodic theorem. We then use this result to get a stronger form of it, namely a very general effective version of Birkhoff's ergodic theorem, which improves all the results previously obtained in this direction, in particular those of V'Yugin, Nandakumar and Hoyrup, Rojas.

Mots clés: Algorithmic randomness; Birkhoff's ergodic theorem; Poincaré recurrence theorem; Martin-Löf randomness

Domaines: Logique en informatique [cs.LO]; Systèmes dynamiques [math.DS]; Probabilités [math.PR]

Laurent Bienvenu, Adam Day, Mathieu Hoyrup, Ilya Mezhirov, Alexander Shen. A constructive version of Birkhoff's ergodic theorem for Martin-Lof random points. Information and Computation, 2012, 210, pp.021-030. ⟨10.1016/j.ic.2011.10.006⟩. ⟨hal-00643629⟩