Local stability of ergodic averages

Authors:
Jeremy Avigad, Philipp Gerhardy and Henry Towsner

Journal:
Trans. Amer. Math. Soc. **362** (2010), 261-288

MSC (2000):
Primary 37A30, 03F60, 03F03

DOI:
https://doi.org/10.1090/S0002-9947-09-04814-4

Published electronically:
July 31, 2009

MathSciNet review:
2550151

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

We consider the extent to which one can compute bounds on the rate of convergence of a sequence of ergodic averages. It is not difficult to construct an example of a computable Lebesgue measure preserving transformation of $[0,1]$ and a characteristic function $f = \chi _A$ such that the ergodic averages $A_n f$ do not converge to a computable element of $L^2([0,1])$. In particular, there is no computable bound on the rate of convergence for that sequence. On the other hand, we show that, for any nonexpansive linear operator $T$ on a separable Hilbert space and any element $f$, it is possible to compute a bound on the rate of convergence of $\langle A_n f \rangle$ from $T$, $f$, and the norm $\| f^* \|$ of the limit. In particular, if $T$ is the Koopman operator arising from a computable ergodic measure preserving transformation of a probability space $\mathcal {X}$ and $f$ is any computable element of $L^2(\mathcal {X})$, then there is a computable bound on the rate of convergence of the sequence $\langle A_n f \rangle$.

The mean ergodic theorem is equivalent to the assertion that for every function $K(n)$ and every $\varepsilon > 0$, there is an $n$ with the property that the ergodic averages $A_m f$ are stable to within $\varepsilon$ on the interval $[n,K(n)]$. Even in situations where the sequence $\langle A_n f \rangle$ does not have a computable limit, one can give explicit bounds on such $n$ in terms of $K$ and $\| f \| / \varepsilon$. This tells us how far one has to search to find an $n$ so that the ergodic averages are “locally stable” on a large interval. We use these bounds to obtain a similarly explicit version of the pointwise ergodic theorem, and we show that our bounds are qualitatively different from ones that can be obtained using upcrossing inequalities due to Bishop and Ivanov.

Finally, we explain how our positive results can be viewed as an application of a body of general proof-theoretic methods falling under the heading of “proof mining.”

- Jeremy Avigad and Solomon Feferman,
*Gödel’s functional (“Dialectica”) interpretation*, Handbook of proof theory, Stud. Logic Found. Math., vol. 137, North-Holland, Amsterdam, 1998, pp. 337–405. MR**1640329**, DOI https://doi.org/10.1016/S0049-237X%2898%2980020-7 - Jeremy Avigad and Ksenija Simic,
*Fundamental notions of analysis in subsystems of second-order arithmetic*, Ann. Pure Appl. Logic**139**(2006), no. 1-3, 138–184. MR**2206254**, DOI https://doi.org/10.1016/j.apal.2005.03.004 - Patrick Billingsley,
*Ergodic theory and information*, Robert E. Krieger Publishing Co., Huntington, N.Y., 1978. Reprint of the 1965 original. MR**524567** - Errett Bishop,
*An upcrossing inequality with applications*, Michigan Math. J.**13**(1966), 1–13. MR**194562** - Errett Bishop,
*Foundations of constructive analysis*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0221878** - Errett Bishop,
*A constructive ergodic theorem*, J. Math. Mech.**17**(1967/1968), 631–639. MR**0228655** - Errett Bishop and Douglas Bridges,
*Constructive analysis*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Springer-Verlag, Berlin, 1985. MR**804042** - Samuel R. Buss (ed.),
*Handbook of proof theory*, Studies in Logic and the Foundations of Mathematics, vol. 137, North-Holland Publishing Co., Amsterdam, 1998. MR**1640324** - Philipp Gerhardy and Ulrich Kohlenbach,
*General logical metatheorems for functional analysis*, Trans. Amer. Math. Soc.**360**(2008), no. 5, 2615–2660. MR**2373327**, DOI https://doi.org/10.1090/S0002-9947-07-04429-7 - Kurt Gödel,
*Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes*, Dialectica**12**(1958), 280–287 (German, with English summary). MR**102482**, DOI https://doi.org/10.1111/j.1746-8361.1958.tb01464.x - Michael Hochman. Upcrossing inequalities for stationary sequences and applications. arXiv:math/0608311v2.
- V. V. Ivanov,
*Oscillations of averages in the ergodic theorem*, Dokl. Akad. Nauk**347**(1996), no. 6, 736–738 (Russian). MR**1398765** - Roger L. Jones, Robert Kaufman, Joseph M. Rosenblatt, and Máté Wierdl,
*Oscillation in ergodic theory*, Ergodic Theory Dynam. Systems**18**(1998), no. 4, 889–935. MR**1645330**, DOI https://doi.org/10.1017/S0143385798108349 - Roger L. Jones, Joseph M. Rosenblatt, and Máté Wierdl,
*Counting in ergodic theory*, Canad. J. Math.**51**(1999), no. 5, 996–1019. MR**1718664**, DOI https://doi.org/10.4153/CJM-1999-044-2 - A. G. Kachurovskiĭ,
*Rates of convergence in ergodic theorems*, Uspekhi Mat. Nauk**51**(1996), no. 4(310), 73–124 (Russian); English transl., Russian Math. Surveys**51**(1996), no. 4, 653–703. MR**1422228**, DOI https://doi.org/10.1070/RM1996v051n04ABEH002964 - Steven Kalikow and Benjamin Weiss,
*Fluctuations of ergodic averages*, Proceedings of the Conference on Probability, Ergodic Theory, and Analysis (Evanston, IL, 1997), 1999, pp. 480–488. MR**1700603** - Yitzhak Katznelson,
*An introduction to harmonic analysis*, 3rd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2004. MR**2039503** - Ulrich Kohlenbach,
*Elimination of Skolem functions for monotone formulas in analysis*, Arch. Math. Logic**37**(1998), no. 5-6, 363–390. Logic Colloquium ’95 (Haifa). MR**1634279**, DOI https://doi.org/10.1007/s001530050104 - Ulrich Kohlenbach,
*Some logical metatheorems with applications in functional analysis*, Trans. Amer. Math. Soc.**357**(2005), no. 1, 89–128. MR**2098088**, DOI https://doi.org/10.1090/S0002-9947-04-03515-9 - U. Kohlenbach,
*Applied proof theory: proof interpretations and their use in mathematics*, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2008. MR**2445721** - Ulrich Kohlenbach. Effective bounds from proofs in abstract functional analysis. To appear in B. Cooper et al., eds.,
*CiE 2005 New Computational Paradigms: Changing Conceptions of What is Computable*, Springer, Berlin. - G. Kreisel,
*On the interpretation of non-finitist proofs. I*, J. Symbolic Logic**16**(1951), 241–267. MR**49135**, DOI https://doi.org/10.2307/2267908 - Georg Kreisel,
*Interpretation of analysis by means of constructive functionals of finite types*, Constructivity in mathematics: Proceedings of the colloquium held at Amsterdam, 1957 (edited by A. Heyting), Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1959, pp. 101–128. MR**0106838** - Ulrich Krengel,
*On the speed of convergence in the ergodic theorem*, Monatsh. Math.**86**(1978/79), no. 1, 3–6. MR**510630**, DOI https://doi.org/10.1007/BF01300052 - Ulrich Krengel,
*Ergodic theorems*, De Gruyter Studies in Mathematics, vol. 6, Walter de Gruyter & Co., Berlin, 1985. With a supplement by Antoine Brunel. MR**797411** - M. G. Nadkarni,
*Spectral theory of dynamical systems*, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser Verlag, Basel, 1998. MR**1719722** - J. A. Nuber,
*A constructive ergodic theorem*, Trans. Amer. Math. Soc.**164**(1972), 115–137. MR**291411**, DOI https://doi.org/10.1090/S0002-9947-1972-0291411-3 - Marian B. Pour-El and J. Ian Richards,
*Computability in analysis and physics*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR**1005942** - Ksenija Simic,
*The pointwise ergodic theorem in subsystems of second-order arithmetic*, J. Symbolic Logic**72**(2007), no. 1, 45–66. MR**2298470**, DOI https://doi.org/10.2178/jsl/1174668383 - Stephen G. Simpson,
*Subsystems of second order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR**1723993** - Bas Spitters,
*A constructive view on ergodic theorems*, J. Symbolic Logic**71**(2006), no. 2, 611–623. MR**2225897**, DOI https://doi.org/10.2178/jsl/1146620162 - Peter Walters,
*An introduction to ergodic theory*, Graduate Texts in Mathematics, vol. 79, Springer-Verlag, New York-Berlin, 1982. MR**648108** - Klaus Weihrauch,
*Computable analysis*, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR**1795407**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
37A30,
03F60,
03F03

Retrieve articles in all journals with MSC (2000): 37A30, 03F60, 03F03

Additional Information

**Jeremy Avigad**

Affiliation:
Department of Philosophy, Carnegie Mellon University, Baker Hall 135, Pittsburgh, Pennsylvania 15213

MR Author ID:
611724

ORCID:
0000-0003-1275-315X

**Philipp Gerhardy**

Affiliation:
Department of Mathematics, University of Oslo, N-0316 Oslo, Norway

**Henry Towsner**

Affiliation:
Department of Mathematics, University of California, Los Angeles, California 90095-1555

Received by editor(s):
December 12, 2007

Published electronically:
July 31, 2009

Additional Notes:
Work by the first author was partially supported by NSF grant DMS-0401042.

Work by the second author was partially supported by a postdoctoral grant from the Villum Kann Rasmussen Foundation.

Article copyright:
© Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.