Ergodic theorems for individual random sequences

V. V. V'yugin

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)

Abstract

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{ω|A(ω)} = 1, where A(ω) is some formula, in "pointwise" form "if ω is random then A(ω) holds". Nevertheless, not all proofs of such laws can be directly translated into the algorithmic form. In [11] two examples have been distinguished -Birkhoff's [2] ergodic theorem and Shannon-McMillan-Breiman theorem of information theory [1]. 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.

Original languageEnglish
Pages (from-to)343-361
Number of pages19
JournalTheoretical Computer Science
Volume207
Issue number2
DOIs
Publication statusPublished - 6 Nov 1998
Externally publishedYes

Keywords

  • Algorithmic information theory
  • Birkhoff's ergodic theorem
  • Individual random sequence
  • Kolmogorov complexity
  • Shannon-McMillan-Breiman theorem

Fingerprint

Dive into the research topics of 'Ergodic theorems for individual random sequences'. Together they form a unique fingerprint.

Cite this