[36] Let f be a function. (a) Show that if the series n 2f(n) converges, then there is a Martin-Lof random sequence such

[36] Let f be a function.

(a) Show that if the series 

n 2−f(n)

converges, then there is a Martin-L¨of random sequence ω such that K(ω1:n) ≤ n + f(n) + O(1), for all n.

(b) Show that 

n 2−f(n) = ∞ iff for every Martin-L¨of random sequence

ω there are infinitely many n such that K(ω1:n) > n + f(n).

Comments. This gives the extent of the upward oscillations of random sequences, in particular the functions f such that the initial n-segment complexity infinitely often exceeds n + f(n). Source: [J.S. Miller and L.

Yu, Advances Math., 226:6(2011), 4816–4840].