Algorithmic randomness and monotone complexity on product space

DOI10.1016/J.IC.2010.10.003MaRDI QIDQ627131zbMATH OpenOpenAlexFDO

Authors H. Takahashi

Publication date 21 February 2011

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.5076

zbMATH Keywords

algorithmic randomnessLambalgen's theoremmonotone complexity

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen's theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, Bayesian statistics for individual random sequences. Formerly Lambalgen's theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Comp. 2008]. In this paper we show the theorem without the assumption.

Review text

The author studies algorithmic randomness and monotone complexity on a product of Cantor spaces. A number of results are proved. The major one is Lambalgen's theorem for correlated probability.

Recommendations

• On a definition of random sequences with respect to conditional probability
• On relative randomness
• Algorithmic randomness over general spaces
• Conditional probabilities and van Lambalgen's theorem revisited
• Uniform test of algorithmic randomness over a general space

Cites work

• Algorithmic Learning Theory
• Can an individual sequence of zeros and ones be random?
• Effective randomness for computable probability measures
• Ergodic theorems for individual random sequences
• scientific article; zbMATH DE number 4054673 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3538599 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 4119313 (Why is no real title available?)
• scientific article; zbMATH DE number 3428899 (Why is no real title available?)
• scientific article; zbMATH DE number 3063387 (Why is no real title available?)
• scientific article; zbMATH DE number 3083069 (Why is no real title available?)
• Mathematical metaphysics of randomness
• On a definition of random sequences with respect to conditional probability
• On equivalence of infinite product measures
• Probability with Martingales
• Process complexity and effective random tests
• Randomness Criteria in Terms of $ {\alpha }$-Divergences
• Redundancy of Universal Coding, Kolmogorov Complexity, and Hausdorff Dimension
• Relations between varieties of kolmogorov complexities
• The definition of random sequences
• The minimum description length principle in coding and modeling
• Von Mises' definition of random sequences reconsidered

Cited in

(6)

• Schnorr randomness for noncomputable measures
• Conditional probabilities and van Lambalgen's theorem revisited
• Layerwise computability and image randomness
• Computable Measure Theory and Algorithmic Randomness
• Conditional measure and the violation of van Lambalgen's theorem for Martin-Löf randomness
• Bayesian definition of random sequences with respect to conditional probabilities

This page was built for publication: Algorithmic randomness and monotone complexity on product space

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