[18] Let A be the set of binary strings of length n. An element x in A is -random if (x|A) , where (x|A)

[18] Let A be the set of binary strings of length n. An element x in A is δ-random if δ(x|A) ≤ δ, where δ(x|A) = n − C(x|A) is the randomness deficiency. Show that if x ∈ B ⊆ A, then log d(A)

d(B) − C(B|A) ≤ δ(x|A) + O(log n).

Comments. That is, no random elements of A can belong to any subset B of A that is simultaneously pure (which means that C(B|A) is small)
and not large (which means that d(A)/d(B) is large). Source: [A.N.
Kolmogorov and V.A. Uspensky, Theory Probab. Appl., 32(1987), 389–
412].