On semimeasures predicting Martin-Löf random sequences

Solomonoff’s central result on induction is that the prediction of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating predictor µ, if the latter is computable. Hence, M is eligible as a universal sequence predictor in the case of unknown µ. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Lof) 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 to µ on 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 µ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.SNF grant 2100-67712 and RFBF grants N04-01-00427 and N02-01-22001