[25] Let x be a string and let S be a finite set containing x. Define S to be strongly typical for x if log d(S) − K(x|S∗) = O(1), where S∗ is the first shortest program to print S in lexicographic lengthincreasing order. (The standard Definition 5.5.3 on page 410 is slightly weaker since it requires log d(S) − K(x|S) to be O(1).) Recall that I(x; S) = K(x) + K(S) − K(x, S) + O(1) is the truly symmetric variant of algorithmic mutual information.

(a) Show that if S is strongly typical for x, then I(x; S) = K(x) −

log d(S) + O(1).

(b) Show that if S is strongly typical for x, then I(x; S) ≥ K(K(x)) −

K(I(x; S)) +O(1) and log d(S) ≤ K(x)− K(K(x)) + K(I(x; S)) +O(1).

(c) Show that S is a sufficient statistic for x iff it is strongly typical and K(S|x∗) = O(1).

(d) Show that if S is a sufficient statistic for x, then I(x; S) = K(S) +

O(1) ≥ K(K(x)) + O(1) and log d(S) ≤ K(x) − K(K(x)) + O(1).

Comments. Item

(d) tells us that every sufficient statistic for x has complexity at least K(K(x)). Source: [P. G´acs, J.T. Tromp, and P.M.B.

Vit´anyi, IEEE Trans. Inform. Theory, 47:6(2001), 2443–2463; Correction, 48:8(2002), 2427].