 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-224/2/a/solution

For an independent identically distributed source with mass function

P

on a finite alphabet and a fixed compression rate

R > H (P)

, the optimal probability of decoding error has exponent

E (R) = min_{Q : H (Q) \geq R} D (Q ∥ P),

meaning that the best fixed-rate codes satisfy

lim_{n \to \infty} - \frac{1}{n} lo g_{2} P_{e}^{(n)} = E (R)

at continuity points of the exponent.

For the direct part, let

m = ∣ A ∣

and

η_{n} = \frac{m l o g _{2} ( n + 1 )}{n} .

Encode every sequence whose type

Q

satisfies

H (Q) \leq R - η_{n}

(n + 1)^{m} 2^{n (R - η_{n})} = 2^{n R},

so they fit into a rate-

R

P_{e}^{(n)} \leq Q : H (Q) > R - η_{n} \sum P^{\otimes n} (T (Q)) \leq (n + 1)^{m} 2^{- n m i n_{Q : H (Q) > R - η_{n}} D (Q ∥ P)} .

Compactness of the probability simplex and continuity of entropy and relative entropy on the support of

P

give

lim inf_{n \to \infty} - \frac{1}{n} lo g_{2} P_{e}^{(n)} \geq min_{Q : H (Q) \geq R} D (Q ∥ P) = E (R),

which is the direct bound.

 New to topics? Read the docs here!