The probability distribution as a computational resource for randomness testing

Abstract

When testing a set of data for randomness according to a probability distribution that depends on a parameter, access to this parameter can be considered as a computational resource. We call a randomness test \emph{Hippocratic} if it is not permitted to access this resource. In these terms, we show that for Bernoulli measures $\mu_p$, $0\le p\le 1$ and the Martin-L\"of randomness model, Hippocratic randomness of a set of data is the same as ordinary randomness. The main idea of the proof is to first show that from Hippocrates-random data one can Turing compute the parameter $p$. However, we show that there is no single Hippocratic randomness test such that passing the test implies computing $p$, and in particular there is no universal Hippocratic randomness test.