A constructive version of Birkhoffs ergodic theorem for Martin-Lof random points

作者：Bienvenu Laurent^*; Day Adam R; Hoyrup Mathieu; Mezhirov Ilya; Shen Alexander

来源：Information and Computation, 2012, 210: 21-30.

DOI：10.1016/j.ic.2011.10.006

• Algorithmic randomness
• Birkhoffs ergodic theorem
• Poincare recurrence theorem
• Martin-Lof randomness

We prove the effective version of Birkhoffs ergodic theorem for Martin-Lof random points and effectively open sets, improving the results previously obtained in this direction (in particular those of Vyugin, Nandakumar and Hoyrup, Rojas). The proof consists of two steps. First, we prove a generalization of Kucera%26apos;s theorem, which is a particular case of effective ergodic theorem: a trajectory of a computable ergodic mapping that starts from a random point cannot remain inside an effectively open set of measure less than 1. Second, we show that the full statement of the effective ergodic theorem can be reduced to this special case. Both steps use the statement of classical ergodic theorem. but not its usual classical proof. Therefore, we get a new simple proof of the effective ergodic theorem (with weaker assumptions than before). %26lt;br%26gt;This result was recently obtained independently by Franklin, Greenberg, Miller and Ng.

• 出版日期2012-1
• 单位INRIA