Algorithmic tests and randomness with respect to a class of measures

DOI10.1134/S0081543811060058zbMath1294.03032arXiv1103.1529WikidataQ57349538 ScholiaQ57349538MaRDI QIDQ2510759

Cristobal Rojas, Mathieu Hoyrup, Laurent Bienvenu, Alexander Shen, Peter Gács

Publication date: 4 August 2014

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

03D32: Algorithmic randomness and dimension

Related Items

Computable Measure Theory and Algorithmic Randomness, Randomness Tests: Theory and Practice, A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE, Bayesian definition of random sequences with respect to conditional probabilities, The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite, Relating and contrasting plain and prefix Kolmogorov complexity, When does randomness come from randomness?, A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points, Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs, Schnorr randomness for noncomputable measures, Conditional probabilities and van Lambalgen's theorem revisited, Layerwise computability and image randomness, Algorithmic identification of probabilities is hard, Randomness deficiencies, On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness, The axiomatic power of Kolmogorov complexity, How much randomness is needed for statistics?, The Kučera-Gács theorem revisited by Levin, Preface: Taming randomness and complexity -- essays in honour of Professor Péter Gács, Computable randomness and betting for computable probability spaces, Algorithmic Statistics: Forty Years Later

Cites Work

• Unnamed Item
• Unnamed Item
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• Test martingales, Bayes factors and \(p\)-values
• Prequential randomness and probability
• On the relation between descriptional complexity and algorithmic probability
• Ergodic theorems for individual random sequences
• Process complexity and effective random tests
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Uniform test of algorithmic randomness over a general space
• Probability and Finance
• Randomness for non-computable measures
• Local stability of ergodic averages
• On-Line Probability, Complexity and Randomness
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Randomness conservation inequalities; information and independence in mathematical theories
• Exact Expressions for Some Randomness Tests
• A Theory of Program Size Formally Identical to Information Theory
• Degrees of unsolvability of continuous functions
• The Existence of Probability Measures with Given Marginals
• Logical basis for information theory and probability theory
• 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