Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 224 / 4

For an IID finite-alphabet source $Q$ and a fixed rate $H(Q)<R<{\log }_2|\mathcal{A}|$, let $P_e^{\ast }(n,R)$ be the smallest probability that a block is not represented by a fixed-to-fixed code having at most $2^{nR}$ codewords. The fixed-rate source-coding error exponent theorem states

For the direct part, encode all type classes whose empirical entropy is at most $R-{\delta }_n$, where ${\delta }_n\downarrow 0$ and $n{\delta }_n-|\mathcal{A}|{\log }_2(n+1)\to \infty$. Since a type class has at most $2^{nH(P)}$ sequences and there are at most $(n+1{)}^{|\mathcal{A}|}$ types, this codebook has at most $2^{nR}$ entries for large $n$. An error can occur only when $H({\hat{P}}_n)>R-{\delta }_n$. The method of types bounds its probability byTaking the lower limit of the exponent and using compactness and continuity gives at least $D^{\ast }(R,Q)$, proving achievability.

Let $Z(\alpha )={\sum }_{x}Q(x{)}^{\alpha }$ and $\ell (x)={\log }_{2}Q(x)$. ThenDifferentiation of this exponential family givesThe first-order terms cancel, leaving

Part b shows that $H(Q_{\alpha })$ decreases continuously from $H(Q_0)={\log }_2|\mathcal{A}|$ to $H(Q_1)=H(Q)$. Because $Q$ is nonuniform, the variance in part b is positive, so for each intermediate $R$ there is a unique ${\alpha }^{\ast }\in (0,1)$ with $H(Q_{{\alpha }^{\ast }})=R$.

To minimize $D(P\Vert Q)$ subject to $H(P)\ge R$, the optimum lies on the boundary $H(P)=R$. The Lagrange multiplier equations forgive $P(x)\propto Q(x{)}^{\alpha }$ for some $\alpha \in (0,1)$. The entropy constraint selects $\alpha ={\alpha }^{\ast }$ uniquely. Therefore