[43] Let be an infinite binary sequence. Show that the following are equivalent to the sequence being random in Martin-Lofs sense (with respect

[43] Let ω be an infinite binary sequence. Show that the following are equivalent to the sequence ω being random in Martin-L¨of’s sense

(with respect to the uniform distribution):

(a) C(ω1:n) ≥ n − K(n) ± O(1) for every n.

(b) γ0(ω1:n|L) = n−C(ω1:n|n)−K(n)+O(1) is finite with L the uniform measure.

(c) For every n and every computable function g such that 
n 2−g(n) <
∞, we have C(ω1:n) ≥ n − g(n) ± O(1), the constant depending on g.

(d) C(ω1:n) ≥ n − G(n) ± O(1) for every n, and a single, appropriately defined, computable function G.
Comments. In Item (b), the formula for γ0 expresses concisely and precisely how the complexity oscillations of C(ω1:n|n) of random infinite sequences behave. This is Levin’s test—the characterization for random sequences from which Theorem 2.5.5 on page 153 follows. Source for Items

(a) and (b): [P. G´acs, Ph.D. thesis, Frankfurt an Main, 1978, Theorem 5.4, Corollary 2; Z. Math. Logik Grundl. Math., 26(1980), 385–
394]. Source for Items (a), (c), and (d): [J.S. Miller and L. Yu, Advances Math., 226:6(2011), 4816–4840]. Another proof of the difficult direction in the last reference is given in [L. Bienvenu, W. Merkle and A.K. Shen, Fundamentae Informatica, 83(2008), 1–4].