Effective Convergence in Probability and an Ergodic Theorem forIndividual Random Sequences

Abstract

An algorithmic analysis of the ergodic theorem for a measure-preserving transformation is given. We prove that the classical ergodic theorem is not algorithmically effective. We present a formulation and a proof of the ergodic theorem for individual random sequences based on A.N. Kolmogorov's algorithmic approach to the substantiation of the theory of probability and information theory.