[31] (a) Show that there is a string x of length n and complexity about 1 2n for which x(O(log n) = 1 4n +

[31]

(a) Show that there is a string x of length n and complexity about 1 2n for which βx(O(log n) = 1 4n + O(log n).

(b) Show that for the set A0 = {0, 1}n we have K(A0) = O(log n) and K(x|A0) = 1 2n + O(log n), and therefore K(A0) + K(x|A0) = 1 2n +

O(log n) is minimal up to a term O(log n).

(c) Show that the randomness deficiency of x in A0 is about 1 2n, which is much bigger than the minimum βx(O(log(n)) ≈ 1 4n.

(d) Show that for the model A1 witnessing βx(O(log(n)) ≈ 1 4n we also have K(A1) = O(log n) and K(x|A1) = 1 2n + O(log n), but log d(A1) =

3 4n + O(log n), which causes the smaller randomness deficiency.

Comments. Ultimate compression of the two-part code in ideal MDL, Section 5.4, means minimizing K(A) + K(x|A) over all models A in the model class. In Theorem 5.5.1 we have essentially shown that the worstcase data-to-model code is the approach that guarantees the best-fitting model. In contrast, the ultimate compression approach can yield models that are far from best fit. It is easy to see that this happens only if the data are not typical for the contemplated model. Hint for Item (a):

use Corollary 5.5.3 on page 419. Source: [N.K. Vereshchagin and P.M.B.

Vit´anyi, Ibid.].