×

Effective aspects of Bernoulli randomness. (English) Zbl 1444.03137

Summary: In this paper, we study Bernoulli random sequences, i.e. sequences that are Martin-Löf random with respect to a Bernoulli measure \(\mu_p\) for some \(p\in [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 (i.e. Martin-Löf 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öf random with respect to \(\mu_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öf random sequence. Lastly, we consider several possible approaches to characterizing blind Bernoulli randomness, where the corresponding Martin-Löf tests do not have access to the Bernoulli parameter \(p\), and show that these fail to characterize blind Bernoulli randomness.

MSC:

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