[43] Sequences with maximal Kolmogorov complexity of the initial segments are random in Martin-L¨of’s sense of passing all effective statistical tests for randomness. Hence, they must satisfy laws like the law of the iterated logarithm.

(a) Show that if ω is an infinite sequence such that Km(ω1:n) = n −
o(ln ln n), then with fn = ω1 + ··· + ωn we have

(b) Show that if Km(ω1:n) = n − o(n), then limn→∞ fn = 1 2 . Conversely, for every > 0 there is an ω with Km(ω1:n) ≥ (1−)n for which the above doesn’t hold.

(c) We say that an infinite binary sequence ω satisfies the infinite recurrence law if fn = 1 2n infinitely often. Let > 0. Prove the following:
(i) If Km(ω1:n) ≥ n − ( 1 2 − ) log n, for all n, then ω is recurrent.
(ii) There is a nonrecurrent ω (fn > 1 2 for all but finitely many n)
such that we have Km(ω1:n) > n − (2 + ) log n, for all n.
Comments. Item

(a) is the law of the iterated logarithm. By Theorem 2.5.6, Item

(a) holds for almost all infinite binary sequences ω. In other words, the law of the iterated logarithm holds for all infinite ω in a set that (obviously strictly) contains the Martin-L¨of random sequences.
Compare this with Equation 2.3 on page 169. There it was shown that for C(x) ≥ n − δ(n), n = l(x), we have |fn − 1 2n| ≤ nδ(n) ln 2. Compare with Exercise 3.5.14 using prefix complexity K. Item

(b) is a form of the strong law of large numbers (Section 1.10). By Theorem 2.5.6 this gives an alternative proof that this law holds for almost all infinite binary sequences. Hint for the second part of Item (b): insert ones in an incompressible sequence at 1/-length intervals. Source: [V.G. Vovk, SIAM Theory Probab. Appl., 32(1987), 413–425].

lim sup |fn-n/2 Vn ln lnn 1 2