Algorithmic identification of probabilities is hard

DOI10.1016/J.JCSS.2018.01.002MaRDI QIDQ1747492zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Santiago Figueira, Benoit Monin, A. Shen

Publication date 8 May 2018

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic randomnessalgorithmic learning theory

Mathematics Subject Classification ID

Computational learning theory (68Q32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Suppose that we are given an infinite binary sequence which is random for a Bernoulli measure of parameter $p$. By the law of large numbers, the frequency of zeros in the sequence tends to~$p$, and thus we can get better and better approximations of $p$ as we read the sequence. We study in this paper a similar question, but from the viewpoint of inductive inference. We suppose now that $p$ is a computable real, but 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 a Turing code). Can one do such a thing uniformly on all sequences that are random for computable Bernoulli measures, or even on a `large enough' fraction of them? In this paper, we give a negative answer to this question. In fact, we prove a very general negative result which extends far beyond the class of Bernoulli measures.

Recommendations

• Algorithmic identification of probabilities is hard
• Algorithmic Probability: Theory and Applications
• scientific article; zbMATH DE number 1283992
• On Empirical Meaning of Randomness with Respect to a Real Parameter
• Identification of probabilities

Cites work

• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• Algorithmic tests and randomness with respect to a class of measures
• An introduction to Kolmogorov complexity and its applications
• Classical recursion theory. Vol. II
• Comparison of identification criteria for machine inductive inference
• Constructive equivalence relations on computable probability measures
• Identification of probabilities
• Learning recursive functions: A survey
• Uniform test of algorithmic randomness over a general space
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)

Cited in

(5)

• Equivalences between learning of data and probability distributions, and their applications
• Algorithmic identification of probabilities is hard
• On the computability of conditional probability
• Identification of probabilities
• Absolutely no free lunches!

This page was built for publication: Algorithmic identification of probabilities is hard

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