[26/38] Let be an infinite binary sequence. (a) Show that is Martin-Lof random iff n 2nK(1:n) < . (b) Let f be

[26/38] Let ω be an infinite binary sequence.

(a) Show that ω is Martin-L¨of random iff 

n 2n−K(ω1:n) < ∞.

(b) Let f be a (possibly incomputable) function such that 
n 2−f(n) = ∞. Assume that ω is random in Martin-L¨of’s sense. Then, K(ω1:n) >
n + f(n) − O(1) for infinitely many n.
Comments. Item

(a) gives a characterization of Martin-L¨of randomness.
Item

(b) is stronger than Item

(d) of Exercise  3.5.3.

Source: [J.S. Miller and L. Yu, Trans. Amer. Math. Soc., 360:6(2008), 3193–3210]. The ‘only if’ side of Item

(a) admits also of a simple proof by martingales due to A.

Nies. The ‘if’ side is immediate from Schnorr’s theorem, Theorem 3.5.1.