[33] (a) Let be a positive computable measure, conditionally bounded away from zero as in Definition 5.2.3 on page 366. Show that for every

[33]

(a) Let μ be a positive computable measure, conditionally bounded away from zero as in Definition 5.2.3 on page 366. Show that for every μ-supermartingale t(x) as in Exercise 5.2.4, and for every number k, the set of infinite binary sequences ω such that there exists a number B (a limit) such that for every  there is an n0 such that for all n>n0 and all x of length less than k we have |t(ω1:nx)− B| <  has μ-measure one.

(b) There exists a positive computable measure μ such that for the μsupermartingale M(x)/μ(x) the set of infinite binary sequences defined in Item

(a) has μ-measure 1 −  with  > 0.

Comments. Item

(a) gives a formulation of the result on off-sequence convergence described in Theorem 5.2.2, Item (ii), on page 366. Namely, M(y|x)/μ(y|x) = t(xy)/t(x) tends to B/B = 1, with t(x) = M(x)/μ(x).

Item

(b) states that the condition “there exists a constant c such that

μ(0|x) >

c, μ(1|x) > c for all x” of Definition 5.2.3 is necessary. Therefore, Item

(a) is the strongest formulation of Theorem 5.2.2, Item (ii):
M(y|x)/μ(y|x) = t(xy)/t(x) tends to B/B = 1, where t(x) = σ(x)/μ(x).
Source: [An.A. Muchnik, Ibid.; M. Hutter and An.A. Muchnik, Theoret.
Comput. Sci., 382:3(2007), 247–261].