[27] Let x = x1 ...xn be obtained by random i.i.d. sampling a sequence X1,...,Xn of n random variables which are all copies of a random variable X. Let X have a finite range X and let Y be a finite set of destination words. Given a distortion function d

(a,

b) with a ∈ X and b ∈ Y extend it to d(x, y) with y = y1y2 ...yn with yi ∈ Yn by d(x, y) = n i=1 d(xi, yi). Let E : Xn → Yn be a prefix-free code.

Define the probabilistic rate distortion by rn(δ) = minE{log d(E(Xn)) :

Ed(x, E(x)) ≤ δ}, the expectation E taken over the probability mass function of the random variable X. Compare below rx(δ) with rn(δ).

(a) Show that almost surely (that is, with probability one) for every δ

the limit limn→∞ rx(δ)/n is equal to rn(δ)/n.

(b) Show that for n → ∞ the limit of the expectation Erx(δ)/n is equal to rn(δ)/n.

Comments. This relates the classical probabilistic approach and the algorithmic approach according to traditional information-theoretic concerns. Source: [E.-H. Yang and S.-Y. Shen, IEEE Trans. Inform. Theory, 39:1(1993), 288–292; J. Muramatsu and F. Kanaya, IEICE Trans. Fundamentals, E77-A:8(1994), 1224–1229; D.M. Sow and A. Eleftheriadis, IEEE Trans. Inform. Theory, 49:3(2003), 604–608].