CONICET | Buscador de Institutos y Recursos Humanos

Suppose that we are given an infinite binary sequence that is random for a Bernoulli measure with parameter $p$. By the law of large numbers, the frequency of ones in the sequence converges to $p$, and thus we can get better and better approximations of $p$ as we read the sequence. We study a similar situation from the viewpoint of inductive inference. We suppose now that $p$ is a computable real, and one asks for more: as we are reading more and more bits of our random sequence, we have to eventually guess the exact parameter $p$ (in the form of its Turing code). Can one do such a thing uniformly for all sequences that are random for computable Bernoulli measures, or even for a ´large enough´ fraction of them? In this paper, we give a negative answer to this question. In fact, we prove a general negative result which extends far beyond the class of Bernoulli measures. We do however provide a weak positive result, by showing that looking at a sequence $X$ generated according to some computable probability measure, we can eventually guess a sequence of measures with respect to which $X$ is random in Martin-Löf´s sense.