The probability of "undefined" (non-converging) output in generating the universal probability distribution

作     者：Solomonoff, Ray J. 

作者机构：Univ London Comp Learning Res Ctr London WC1E 7HU England IDSIA CH-6928 Manno Lugano Switzerland 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2008年第106卷第6期

页      面：238-240页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：algorithmic probability analysis of algorithms halting problem incomputable Kolmogorov complexity normalization theory of computation Turing machine universal probability distribution universal Turing machine 

摘      要：In order to generate a universal probability distribution to extrapolate a binary string x of length i, we feed random bits into a universal device, M. When we find an input string that gives an output matching x, we continue the successful input with random bits until M produces a zero or one as output. The relative probabilities of these two continuations can give a normalized prediction for the probability of the symbol following x. There is, however, a probability, Pi+l (u) that the continued random input string will not generate any output for the (i + l)th symbol. We will show E-mu Sigma(n)(i=l) P-i((u)) = k(mu) ln 2. Here E-mu is the expected value with respect to mu, the probability distribution that created x. k(mu) is the Kolmogorov complexity of mu with respect to M. n is any positive integer. Usually we do not know mu and so we do not know k(mu). However, if mu is the uniform distribution, we can usually find a good upper bound for k(mu). Published by Elsevier B.V.