[27] Define S n (a) = l(x)=n1 (x)(M(a|x) (a|x))2, with a B, with B the basic alphabet used in Theorem 5.2.1 on

• [27] Define S

n

(a) = 

l(x)=n−1 μ(x)(M(a|x) − μ(a|x))2, with a ∈ B, with B the basic alphabet used in Theorem 5.2.1 on page 360.

Let S

n = 

a∈B S

n(a). This is the summed expected squared difference.

(a) Show that if B = {0, 1} then 

n S

n(0), S

n(1) ≤ 1 2K(μ) ln 2.

(b) Show that for every finite, possibly nonbinary, alphabet



B we have n S

n ≤ K(μ) ln 2.

Comments. The definition of S
n is based on the Euclidean distance between two probability distributions P and Q over B, defined as E(P, Q) = 2
a∈B(P

(a) − Q(a))231/2 . Item

(a) is Solomonoff’s original version of Theorem 5.2.1 using the squared difference rather than the absolute difference. This was used in earlier editions of this book. Source for Item (a): [R.J. Solomonoff, IEEE Trans. Inform. Theory, 24(1978), 422–432].
Source for Item (b): [M. Hutter, Proc. 12th Europ. Conf. Mach. Learn., Lect. Notes Artif. Int., Vol. 2167, Springer-Verlag, 2001].