Effective aspects of Bernoulli randomness

摘要

In this paper, we study Bernoulli random sequences, i.e. sequences that are Martin-Lof random with respect to a Bernoulli measure mu(p) for some p is an element of [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-Lof 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-Lof 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-Lof random sequence. Lastly, we consider several possible approaches to characterizing blind Bernoulli randomness, where the corresponding Martin-Lof tests do not have access to the Bernoulli parameter p, and show that these fail to characterize blind Bernoulli randomness.