[29] Let limn 1 n n i=1 i = p for an infinite binary sequence = 12 ..., for some p between 0 and

[29] Let limn→∞ 1 n

n i=1 ωi = p for an infinite binary sequence

ω = ω1ω2 ..., for some p between 0 and 1 (compare Section 1.9).

(a) Show that if C(ω1:n) ∼ n, then p = 1 2 .

(b) Show that if p = 1 4 , then C(ω1:n) ≤ 0.82n asymptotically.

(c) Show that in general, if c = p log 1/p + (1 − p) log 1/(1 − p), then C(ω1:n) ≤ cn + o(n). If p is about 1 4 , then C(ω1:n) ≤ 0.80n + o(n).

Comments. Source: [P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987]; attributed to A.N. Kolmogorov. Hint for Item (a): use Lemma 2.6.2.