The probability distribution as a computational resource for randomness testing

DOI10.4115/JLA.2010.2.10MaRDI QIDQ3145956zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen

Publication date 17 December 2012

Published in Journal of Logic and Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1408.2850

zbMATH Keywords

algorithmic randomnessBernoulli distributionlaw of large numbersMartin-Löf randomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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 $m{u}_p$, $0leple1$ 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.

Recommendations

• On Empirical Meaning of Randomness with Respect to a Real Parameter
• On empirical meaning of randomness with respect to parametric families of probability distributions
• Uniform test of algorithmic randomness over a general space

Cited in

(11)

• Schnorr randomness for noncomputable measures
• Conditional probabilities and van Lambalgen's theorem revisited
• On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness
• When does randomness come from randomness?
• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• Computable Measure Theory and Algorithmic Randomness
• Conditional measure and the violation of van Lambalgen's theorem for Martin-Löf randomness
• Bayesian definition of random sequences with respect to conditional probabilities
• Unprincipled
• Redundancy of information: lowering effective dimension

This page was built for publication: The probability distribution as a computational resource for randomness testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3145956)