[M19] Let f be such that 2f(n) < . Show that the set of infinite binary sequences satisfying C(1:n|n) n f(n) for

[M19] Let f be such that 2−f(n) < ∞. Show that the set of infinite binary sequences ω satisfying C(ω1:n|n) ≥ n − f(n) for all but finitely many n has uniform measure 1.

Comments. Hint: The number of y with l(y) = n such that C(y) <

n − f(n) is less than 2n−f(n)

. This implies that the probability that this inequality is satisfied is less than 2−f(n)
, and the result follows by the Borel–Cantelli lemmas; see Exercise 1.10.2 on page 64. This set of ω’s properly contains the set defined by Theorem