Ergodic theorems for individual random sequences

DOI10.1016/S0304-3975(98)00072-3zbMath0915.68092MaRDI QIDQ1275009

Vladimir V. V'yugin

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

algorithmic information theoryKolmogorov complexityShannon-McMillan-Breiman theoremBirkhoff's ergodic theoremindividual random sequence

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

On stability of probability laws with respect to small violations of algorithmic randomness ⋮ UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS ⋮ USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS ⋮ A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE ⋮ Numeration and discrete dynamical systems ⋮ Algorithmic randomness and monotone complexity on product space ⋮ Lowness, Randomness, and Computable Analysis ⋮ Computability theory. Abstracts from the workshop held January 7--13, 2018 ⋮ A Characterization of Constructive Dimension ⋮ Uncomputably noisy ergodic limits ⋮ Randomness and Determination, from Physics and Computing towards Biology ⋮ Algorithmic tests and randomness with respect to a class of measures ⋮ A characterization of constructive dimension ⋮ The metamathematics of ergodic theory ⋮ From exact sciences to life phenomena: Following Schrödinger and Turing on programs, life and causality ⋮ Randomness and the Ergodic Decomposition ⋮ Non-stochastic infinite and finite sequences ⋮ Computable randomness and betting for computable probability spaces ⋮ Effective symbolic dynamics, random points, statistical behavior, complexity and entropy ⋮ Oscillation and the mean ergodic theorem for uniformly convex Banach spaces ⋮ Computable Measure Theory and Algorithmic Randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Shannon-McMillan-Breiman theorem for a class of amenable groups
• Process complexity and effective random tests
• Can an individual sequence of zeros and ones be random?
• Combinatorial foundations of information theory and the calculus of probabilities
• The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences
• Algorithms and Randomness
• Exact Expressions for Some Randomness Tests
• Subadditive mean ergodic theorems
• Logical basis for information theory and probability theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences