首页 | 本学科首页   官方微博 | 高级检索  
     


On semimeasures predicting Martin-Löf random sequences
Authors:Marcus Hutter  Andrej Muchnik
Affiliation:1. IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland;2. RSISE/ANU/NICTA, Canberra, ACT, 0200, Australia;3. Institute of New Technologies, 10 Nizhnyaya Radischewskaya, Moscow 109004, Russia
Abstract:Solomonoff’s central result on induction is that the prediction of a universal semimeasure MM converges rapidly and with probability 1 to the true sequence generating predictor μμ, if the latter is computable. Hence, MM 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-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of MM itself. We show that there are universal semimeasures MM 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 DD as a mixture over all computable measures and the enumerable semimeasure WW as a mixture over all enumerable nearly measures. We show that WW converges to DD and DD to μμ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.
Keywords:Sequence prediction  Algorithmic information theory  Universal enumerable semimeasure  Mixture distributions  Predictive convergence  Martin-Lö  f randomness  Supermartingales  Quasimeasures
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号