[20] Consider strings x of length n. Define the conditional variant of Definition 5.5.6 on page 413 as hx(i|y) = minS{log d(S) : S x, d(S) < ∞, K(S|y) ≤ i}. Since S1 = {0, 1}n is a set containing x and can be described by O(1) bits (given n), we find that hx(i|n) ≤ n for i = K(S1|n) = O(1). For increasing i, the size of a set S x, which one can describe in i bits, decreases monotonically until for some i0 we obtain a first set S0 witnessing hx(i0|n) + i0 = K(x|n) + O(1). Then, S0 is a minimal sufficient statistic for x.

(a) Consider i ≥ i0. Show that every increase of i about halves the witness set Si of hx(i|n), for each additional bit of i, until i = K(x|n), in the sense that hx(i0 + d|n) = K(x|n) − (i0 + d + O(log d)), provided the right-hand side is nonnegative, and 0 otherwise.

(b) Show that the number of different sufficient statistics for x is bounded by a universal constant independent of x. Argue that this causes the little bumps in the sufficient statistic region ⊆ [K(K(x)), K(x)] in Figure 5.5.

Comments. Source: Item

(a) [N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.], and Item (b): [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].