[27] Let be a computable measure over B. We use M to estimate the probabilities (a|y) for a B and y B.

• [27] Let μ be a computable measure over B∞. We use M to estimate the probabilities μ(a|y) for a ∈ B and y ∈ B∗. Show that for every n,



l(x)=n μ(x)

n i=1 M(u|x1:i−1) ≤ K(μ) ln 2, where we define x1:0 =  and M(u|x1:i−1)=1 − 

a∈B M(a|x1:i−1).

Comments. Let μ be an unknown computable measure, and suppose we are given a string x = x1 ...xn. We can use M(a|x1:i−1) to predict μ(a|x1:i−1) (a ∈ B and 1 ≤ i ≤ n). But M being a semimeasure, we can have 

a∈B M(a|x) < 1. Exercise 4.5.6, with B = {0, 1}, shows that M(x)/(M(x0) + M(x1)) can be very large, so the universal probability that after printing x the reference monotonic machine will never print again, M(xu) = M(x) − M(x0) − M(x1) with u the next symbol being ‘undefined,’ is close to 1. The current exercise shows that this occurs only rarely, and for long sequences produced according to computable measure μ these occurrences do not have much μ-probability.

Indeed, 

l(x)=n μ(x)

n i=1 M(u|x1:i−1) < n i=1 1/i for growing n. Hint:

In Section 4.5.3 we defined the normalized version Mnorm(x) with x =

x1 ...xn by Equation 4.14 on page 308. Consider the negative Kullback–

Leibler divergence −D(μ  Mnorm) ≤ 0 for strings of length n. Substituting Mnorm of Equation 4.14, we obtain −D(μ  M) + 

l(x)=n

μ(x)

n i=1 ln(1/(1−M(u|x1:i−1))) ≤ 0. Using Corollary 4.5.1 on page 307, we can show that D(μ  M) ≤ K(μ) ln 2. Adding the last two inequalities, we obtain 

l(x)=n μ(x)

n i=1 ln(1/(1 − M(u|x1:i−1))) ≤ K(μ) ln 2.

Since − ln(1−z) = z+(z2/2)+(z3/3)+··· , we obtain 

l(x)=n μ(x)

n



i=1 ∞

j=1 (M(u|x1:i−1))j ≤ K(μ) ln 2. Since all terms are positive, we obtain



l(x)=n μ(x)

n i=1 M(u|x1:i−1) ≤ K(μ) ln 2. Source: [R.J. Solomonoff, Inform. Process. Lett., 106:6(2008), 238–240].