[31] Let the probability that an initial segment x of a binary sequence is followed by a ∈ {0, 1}∗ be M(a|x) = M(xa)/M(x).

(a) Show that there is a constant c > 0 such that the probability (with respect to M) of the next bit being 0 after 0n is at least c.

(b) Show that there exists a constant c such that the probability (with respect to M) of the next bit being 1 after 0n is at least 1/(cn log2 n).

(c) Show that for every constant c and sufficiently large N, there are at most N/c initial segments 0n (1 ≤ n ≤ N) such that the probability

(with respect to M) of the next bit being 1 is larger than (c log2 n)/n.

(d) Conclude that the probability (with respect to M) of the next bit following 0n being 1 is f(n)/n with f(n) = Ω(1/ log2 n)

 O(log2 n).

Comments. This exercise is a simple form of Occam’s razor: The conditional M probability assigns high probability to the simple explanations and low probability to the complex explanations. The assertion Item (d)

is an M prior probability variant of P.S. Laplace’s well-known exercise to compute the expectation of a successful trial following n successful trials in a Bernoulli process (p, 1 − p) with unknown p. Using Bayes’s rule with uniform prior probability, this expectation is (n + 1)/(n + 2)

and is a special case of Laplace’s law of succession (Exercise 1.10.6 on page 65). Application of this law sets the probability of a 1 following n initial 0’s at 1/(n + 2). This is fairly close to the approximation we found in Item

(d) using conditional M probability. In A Philosophical Essay on Probabilities, Laplace uses this rule to compute the probability that the sun will not rise tomorrow, given that it has been rising every morning since the creation of the world 10,000 years ago. It follows that the probability that the sun will not rise tomorrow is approximately 1/3,650,000. This is correct, in case our information about the sun were exhausted by the fact stated. Hint for Items

(a) through (c): use |K(x) − log 1/M(x)| ≤ 2 log K(x) + O(1). For all n we have K(0n1) ≤ log n + 2 log log n + O(1), and for the majority of n we have K(0n1) ≥ log n. Source: [L.A. Levin and A.K. Zvonkin, Russ. Math.
Surveys, 25:4(1970), 83–124; see also T.M. Cover and J.A. Thomas, Elements of Information Theory, Wiley, 1991].