2026-07-24T05:07:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14520 2024-03-06T10:54:13Z ddc:004 open_access

Ergodic Theorems and Converses for PSPACE Functions Nandakumar, Satyadev Pulari, Subin Ergodic Theorem Resource-bounded randomness Computable analysis Complexity theory We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow [Ulrich Krengel, 1978]. In contrast, we show that for a class of PSPACE L¹ functions, and a class of PSPACE computable measure-preserving ergodic transformations, the ergodic average exists and is equal to the space average on every EXP random. We establish a partial converse that PSPACE non-randomness can be characterized as non-convergence of ergodic averages. Further, we prove that there is a class of resource-bounded randoms, viz. SUBEXP-space randoms, on which the corresponding ergodic theorem has an exact converse - a point x is SUBEXP-space random if and only if the corresponding effective ergodic theorem holds for x. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satyadev Nandakumar and Subin Pulari 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.80 urn:nbn:de:0030-drops-145204 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.80 eng https://creativecommons.org/licenses/by/4.0/legalcode