[29] Let = 12 ... be an infinite binary sequence and let c() be the smallest c for which K(1:n) n c.

[29] Let ω = ω1ω2 ... be an infinite binary sequence and let c(ω) be the smallest c for which K(ω1:n) ≥ n −

c. Let ω be Martin-L¨of random with respect to the uniform distribution. Let S(n) = n i=1 ωi.

(a) Show that given  > 0, we can compute an n

(c, ) such that

(b) Show that for given λ > 1, we can compute an n

(c, λ) such that

(c) Show that for given λ < 1, we can compute an n

(c, λ) such that Comments. Source: Suggested by J.T. Tromp probably following [G.

Davie, Ann. Probab., 29:4(2001), 1426–1434]. This is the law of the iterated logarithm (Exercise 1.10.5 on page 65). See also Exercise 4.5.16 on page 334 proving the above for sequences with high Km-complexity (but so low that they strictly contain the Martin-L¨of random sequences).