Constraints placed on random sequences by their compressibility

DOI10.1016/J.SPL.2012.04.009zbMATH Open1256.03046OpenAlexW1980120528MaRDI QIDQ449434FDOQ449434

Authors: 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

Recommendations

• A level of Martin-Lof randomness.
• Statistical properties of finite sequences with high Kolmogorov complexity
• Everywhere complex sequences and the probabilistic method
• Chaitin complexity, Shannon information content of a single event, and infinite random sequences. II
• Binary sequences. I: Complexity

zbMATH Keywords

large deviationscompressibilityalgorithmically random sequenceprobability laws

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Compressibility of Deterministic and Random Infinite Sequences
• Compressibility of random walker trajectories on growing networks
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449434)