[35] Let r() be the function shown in Figure 8.1 on page 638. (a) Show that K(r) = O(log n), and that r satisfies the

[35] Let r(δ) be the function shown in Figure 8.1 on page 638.

(a) Show that K(r) = O(log n), and that r satisfies the conditions of Exercise 8.1.10.

(b) Show that the rate-distortion graph rx(δ) of the string x existing by Exercise 8.1.10 is in the strip of size O(

√n log n) of the graph of r(δ).

Therefore, rx(δ) is almost constant for 1 6 ≤ δ ≤ 1 3

(c) Show that for the x of Item (b), the number of bits we have to transmit for a string within Hamming distance 1 3 is about equal to that we have to transmit for a string within Hamming distance 1 6 .

(d) Show that only if the fraction of incorrect bits with respect to x is allowed to be sufficiently greater than 1 3 can we save in the number of transmitted bits.
Comments. Source: [N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.].