Annals of Pure and Applied Logic 160 (3):238-254 (2009)

A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2009.01.002
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,436
Through your library

References found in this work BETA

Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.

Add more references

Citations of this work BETA

Bayesian Merging of Opinions and Algorithmic Randomness.Francesca Zaffora Blando - forthcoming - British Journal for the Philosophy of Science.
Computable Randomness and Betting for Computable Probability Spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.
Luzin’s (N) and Randomness Reflection.Arno Pauly, Linda Westrick & Liang Yu - 2022 - Journal of Symbolic Logic 87 (2):802-828.

Add more citations

Similar books and articles

Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Borel Equivalence Relations Which Are Highly Unfree.Greg Hjorth - 2008 - Journal of Symbolic Logic 73 (4):1271-1277.
Maximal R.E. Equivalence Relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
? 0 N -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
WHAT IS. . . A Halting Probability?Cristian S. Calude - 2010 - Notices of the AMS 57:236-237.
Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
$\sum_{0}^{N}$ -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351 - 358.
On Bounded Type-Definable Equivalence Relations.Ludomir Newelski & Krzysztof Krupi?Ski - 2002 - Notre Dame Journal of Formal Logic 43 (4):231-242.


Added to PP index

Total views
13 ( #772,731 of 2,520,399 )

Recent downloads (6 months)
1 ( #405,718 of 2,520,399 )

How can I increase my downloads?


My notes