Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems

Stefano Galatolo
(Dipartiento di matematica applicata, Universita di Pisa)
Mathieu Hoyrup
(LORIA, Vandoeuvre-l es-Nancy, France)
Cristóbal Rojas
(Fields Institute, Toronto, Canada)

A pseudorandom point in an ergodic dynamical system over a computable metric space is a point which is computable but its dynamics has the same statistical behavior as a typical point of the system.

It was proved in [Avigad et al. 2010, Local stability of ergodic averages] that in a system whose dynamics is computable the ergodic averages of computable observables converge effectively. We give an alternative, simpler proof of this result.

This implies that if also the invariant measure is computable then the pseudorandom points are a set which is dense (hence nonempty) on the support of the invariant measure.

Invited Presentation in Xizhong Zheng and Ning Zhong: Proceedings Seventh International Conference on Computability and Complexity in Analysis (CCA 2010), Zhenjiang, China, 21-25th June 2010, Electronic Proceedings in Theoretical Computer Science 24, pp. 7–18.
Published: 3rd June 2010.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: