Constraints placed on random sequences by their compressibility

DOI10.1016/J.SPL.2012.04.009MaRDI QIDQ449434zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)