Constructive equivalence relations on computable probability measures

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

Abstract

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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,934

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Computable randomness and betting for computable probability spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.
Algorithmic randomness over general spaces.Kenshi Miyabe - 2014 - Mathematical Logic Quarterly 60 (3):184-204.
Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
Bernoulli randomness and Bernoulli normality.Andrew DeLapo - 2021 - Mathematical Logic Quarterly 67 (3):359-373.
Randomness notions and reverse mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.
Continuous higher randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.

Analytics

Added to PP
2013-12-22

Downloads
56 (#390,570)

6 months
18 (#171,240)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

References found in this work

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

Add more references