On a definition of random sequences with respect to conditional probability

DOI10.1016/j.ic.2008.08.003zbMath1208.03046OpenAlexW2048211742MaRDI QIDQ999259

Hayato Takahashi

Publication date: 3 February 2009

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

Full work available at URL: https://doi.org/10.1016/j.ic.2008.08.003

zbMATH Keywords

Kolmogorov complexityconditional probabilityMartin-Löf randomnessFubini's theoremrelativized randomness

Mathematics Subject Classification ID

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

Related Items

When does randomness come from randomness? ⋮ UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS ⋮ A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE ⋮ Schnorr randomness for noncomputable measures ⋮ Bayesian definition of random sequences with respect to conditional probabilities ⋮ Conditional probabilities and van Lambalgen's theorem revisited ⋮ Algorithmic randomness and monotone complexity on product space ⋮ Conditional measure and the violation of van Lambalgen's theorem for Martin-Löf randomness ⋮ Computable Bayesian Compression for Uniformly Discretizable Statistical Models ⋮ Excess entropy in natural language: Present state and perspectives ⋮ Computable Measure Theory and Algorithmic Randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kolmogorov's contributions to information theory and algorithmic complexity
• Process complexity and effective random tests
• Can an individual sequence of zeros and ones be random?
• Von Mises' definition of random sequences reconsidered
• Algorithms and Randomness
• Probability with Martingales
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences