Computer Science – Information Theory
Scientific paper
2007-08-17
Theoretical Computer Science, 382 (2007) 247-261
Computer Science
Information Theory
21 LaTeX pages
Scientific paper
Solomonoff's central result on induction is that the posterior of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown mu. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Loef) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M itself. We show that there are universal semimeasures M which do not converge for all random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D as a mixture over all computable measures and the enumerable semimeasure W as a mixture over all enumerable nearly-measures. We show that W converges to D and D to mu on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.
Hutter Marcus
Muchnik Andrej
No associations
LandOfFree
On Semimeasures Predicting Martin-Loef Random Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Semimeasures Predicting Martin-Loef Random Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Semimeasures Predicting Martin-Loef Random Sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-5737