pith. sign in

arxiv: 1408.2850 · v1 · pith:AAFUFQ2Snew · submitted 2014-08-12 · 🧮 math.LO

The probability distribution as a computational resource for randomness testing

classification 🧮 math.LO
keywords randomnesshippocratictestdataparameterresourceaccesscomputational
0
0 comments X
read the original 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 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.