Effective aspects of Bernoulli randomness

DOI10.1093/LOGCOM/EXZ021MaRDI QIDQ5212559zbMATH OpenOpenAlexWikidataFDO

Authors Christopher P. Porter

Publication date 29 January 2020

Published in Journal Of Logic And Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Martingales with discrete parameter (60G42) Random measures (60G57)

Abstract: In this paper, we study Bernoulli random sequences, i.e., sequences that are Martin-L"of random with respect to a Bernoulli measure $m{u}_p$ for some $pin[0,1]$, where we allow for the possibility that $p$ is noncomputable. We focus in particular on the case in which the underlying Bernoulli parameter $p$ is proper (that is, Martin-L"of random with respect to some computable measure). We show for every Bernoulli parameter $p$, if there is a sequence that is both proper and Martin-L"of random with respect to $m{u}_p$, then $p$ itself must be proper, and explore further consequences of this result. We also study the Turing degrees of Bernoulli random sequences, showing, for instance, that the Turing degrees containing a Bernoulli random sequence do not coincide with the Turing degrees containing a Martin-L"of random sequence. Lastly, we consider several possible approaches to characterizing blind Bernoulli randomness, where the corresponding Martin-L"of tests do not have access to the Bernoulli parameter $p$, and show that these fail to characterize blind Bernoulli randomness.

Recommendations

• Bernoulli randomness and Bernoulli normality
• scientific article; zbMATH DE number 4027455
• Algorithmic tests and randomness with respect to a class of measures
• Some results on effective randomness
• TT-functionals and Martin-Löf randomness for Bernoulli measures

Cited in

(6)

• TT-functionals and Martin-Löf randomness for Bernoulli measures
• Algorithmic identification of probabilities is hard
• On the concept of the Bernoulli property
• Bernoulli randomness and Bernoulli normality
• Unprincipled
• Redundancy of information: lowering effective dimension

This page was built for publication: Effective aspects of Bernoulli randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212559)