Computability of convergence rates in the ergodic theorem for Martin-Löf random points

George Davie


In this paper we look at the convergence rates for the ergodic averages in the pointwise ergodic theorem for computable ergodic transformations on the unit interval. While these rates are layerwise computable for Martin-Löf random points and effectively open sets with Lebesgue measure a computable real, they are also layerwise computable for an arbitrary interval. There are however, effectively open sets for which there are \emph{no} effective rates, in particular, not layerwise computable ones. We also show that, when the  measure of the effectively open set is any real $\alpha$, the convergence rates are computable in $\alpha$ and the layers relative to $\alpha$.


Layerwise Computable; Martin-Lof random; Ergodic Theorem; Effectively open set; Effective convergence rates.

Full Text:

2. [PDF]


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN:  1759-9008