Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 323 / 1 / a / Solution

A rate-$R$ block code consists of an encoder $E_n:J^n\to \{1,\dots ,M_n\}$ and decoder $D_n$, with $M_n\le 2^{nR}$; it is reliable when $\mathrm{Pr}[D_n(E_n(U^n))\ne U^n]\to 0$. Choose $\epsilon >0$ with $H(U)+\epsilon <R$. The typical set has probability tending to one and cardinality at most $2^{n(H(U)+\epsilon )}\le 2^{nR}$. Encode its words injectively and map every atypical word to a default codeword. The error probability is at most the atypical probability, so reliable compression exists.