An Ergodic Theorem for PSPACE functions.
Satyadev Nandakumar, Subin Pulari · arXiv (Cornell University) · 2020
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence to the ergodic averages for integrable functions can in general, be arbitrarily slow. However, we show that for PSPACE L1 functions and a class of PSPACE computable measure-preserving ergodic transformations, the ergodic average exists and is equal to the space average on every EXPSPACE random. Further, we show that the class of EXPSPACE randoms is a strict subset of the class of PSPACE randoms studied by Huang and Stull.