An effective ergodic theorem and some applications
Satyadev Nandakumar · 2008
This work is a synthesis of recent advances in computable analysis with the theory of algorithmic randomness. In this theory, we try to strengthen probabilistic laws, i.e., laws which hold with probability 1, to laws which hold in their pointwise effective form - i.e., laws which hold for every individual constructively random point. In a tour-de-force, V'yugin proved an effective version of the Ergodic Theorem which holds when the probability space, the transformation and the random variable are computable. However, V'yugin's Theorem cannot be directly applied to many examples, because all computable functions are continuous, and many applications use discontinuous functions.