Constraints placed on random sequences by their compressibility

DOI10.1016/j.spl.2012.04.009zbMath1256.03046MaRDI 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 deviations; compressibility; algorithmically random sequence; probability laws

Mathematics Subject Classification ID

60G50: Sums of independent random variables; random walks

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

60F10: Large deviations

60A05: Axioms; other general questions in probability

03D32: Algorithmic randomness and dimension

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