Constraints placed on random sequences by their compressibility

DOI10.1016/j.spl.2012.04.009zbMath1256.03046OpenAlexW1980120528MaRDI QIDQ449434

George Davie

Publication date: 30 August 2012

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.spl.2012.04.009

zbMATH Keywords

large deviationscompressibilityalgorithmically random sequenceprobability laws

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Large deviations (60F10) Axioms; other general questions in probability (60A05) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
• New applications of the incompressibility method. II
• Uniform test of algorithmic randomness over a general space
• A computable version of the random signs problem and Kolmogorov complexity
• Algorithmic Randomness and Complexity
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences
• A Theory of Program Size Formally Identical to Information Theory
• Computability and Randomness
• The definition of random sequences
• A formal theory of inductive inference. Part I
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Constraints placed on random sequences by their compressibility