[09] Consider infinite binary sequences with respect to the uniform measure. Show that with probability one there exists a constant c such that C(1:n|n)

[09] Consider infinite binary sequences ω with respect to the uniform measure. Show that with probability one there exists a constant c such that C(ω1:n|n) ≥ n − c for infinitely many n.

Comments. Hint: Use Theorem 2.5.6, Item (ii), and Claim 2.5.1.

Source:

[P. Martin-L¨of, Ibid.].