01238746

j

01238746 V'yugin, V.V. Ergodic theorems for individual random sequences. Theor. Comput. Sci. 207, No.2, 343-361 (1998). 1998 Elsevier Science Publishers, Amsterdam EN individual random sequence Birkhoff's ergodic theorem Shannon-McMillan-Breiman theorem Kolmogorov complexity algorithmic information theory

doi:10.1016/S0304-3975(98)00072-3

Summary: In the framework of the Kolmogorov's approach to the substantiation of the probability theory and information theory on the base of the theory of algorithms we try to formulate probabilistic laws, i.e. statements of the form P{$\omega \mid$A($\omega)$}=1, where $A(\omega)$ is some formula, in ``pointwise'' form ``if $\omega$ is random then $A(\omega)$ holds''. Nevertheless, not all proofs of such laws can be directly translated into the algorithmic form. In {\it M. Lambalgen}, Random Sequences (Amsterdam, 1987) two examples have been distinguished -- Birkhoff's ergodic theorem and Shannon-McMillan-Breiman theorem of information theory. In this paper an analysis of algorithmic effectiveness of these theorems is given. We prove that Birkhoff's ergodic theorem is indeed in some strong sense ``nonconstructive''. At the same time the claim to formulate probabilistic laws for algorithmically random sequences is not so restrictive. We present the versions of these laws for individual random sequences.