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, 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 very general negative result which extends far beyond the class of Bernoulli measures.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Gács, P.: Uniform test of algorithmic randomness over a general space. Theoretical Computer Science 341(1-3), 91–137 (2005)
Li, M., Vitányi, P.: An introduction to Kolmogorov complexity and its applications, 3rd edn. Texts in Computer Science. Springer, New York (2008)
Vitanyi, P., Chater, N.: Algorithmic identification of probabilities (2013), http://arxiv.org/abs/1311.7385
Weihrauch, K.: Computable analysis. Springer, Berlin (2000)
Zeugmann, T., Zilles, S.: Learning recursive functions: a survey. Theoretical Computer Science 397, 4–56 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bienvenu, L., Monin, B., Shen, A. (2014). Algorithmic Identification of Probabilities Is Hard. In: Auer, P., Clark, A., Zeugmann, T., Zilles, S. (eds) Algorithmic Learning Theory. ALT 2014. Lecture Notes in Computer Science(), vol 8776. Springer, Cham. https://doi.org/10.1007/978-3-319-11662-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-11662-4_7
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11661-7
Online ISBN: 978-3-319-11662-4
eBook Packages: Computer ScienceComputer Science (R0)