Algorithmic identification of probabilities is hard
2018
Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter , we can get better and better approximations of using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that is a computable real, and we have to eventually guess the program that computes . We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes Martin-Löf random.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI