Algorithmic tests and randomness with respect to a class of measures

DOI10.1134/S0081543811060058zbMath1294.03032arXiv1103.1529OpenAlexW1854153889WikidataQ57349538 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

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

Related Items (21)

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? ⋮ Randomness Tests: Theory and Practice ⋮ 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 ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Conditional probabilities and van Lambalgen's theorem revisited ⋮ Layerwise computability and image randomness ⋮ A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points ⋮ Preface: Taming randomness and complexity -- essays in honour of Professor Péter Gács ⋮ Algorithmic Statistics: Forty Years Later ⋮ The axiomatic power of Kolmogorov complexity ⋮ How much randomness is needed for statistics? ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Algorithmic identification of probabilities is hard ⋮ Randomness deficiencies ⋮ Computable randomness and betting for computable probability spaces ⋮ On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness ⋮ Computable Measure Theory and Algorithmic Randomness

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

This page was built for publication: Algorithmic tests and randomness with respect to a class of measures