Ergodic theorems and converses for PSPACE functions

DOI10.1007/s00224-022-10094-9OpenAlexW4293769876WikidataQ113906001 ScholiaQ113906001MaRDI QIDQ6109066

Subin Pulari, Satyadev Nandakumar

Publication date: 26 July 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10094-9

zbMATH Keywords

ergodic theoremcomplexity theorycomputable analysisresource-bounded randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• Upcrossing inequalities for stationary sequences and applications
• A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties
• On the speed of convergence in the ergodic theorem
• Computability of probability measures and Martin-Löf randomness over metric spaces
• A short proof of Pillai's theorem on normal numbers
• Randomness and Non-ergodic Systems
• The dimension of ergodic random sequences
• Algorithmic Randomness and Complexity
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Von Mises' definition of random sequences reconsidered
• The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей
• Polynomial Space Randomness in Analysis
• An analogue of Pillai's theorem for continued fraction normality and an application to subsequences

This page was built for publication: Ergodic theorems and converses for PSPACE functions