Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 224 / 2

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 exponentmeaning that the best fixed-rate codes satisfyat continuity points of the exponent.

For the direct part, let $m=|A|$ andEncode every sequence whose type $Q$ satisfies $H(Q)\le R-{\eta }_n$. The method of types bounds the number of such sequences byso they fit into a rate-$R$ codebook. The error probability obeysCompactness of the probability simplex and continuity of entropy and relative entropy on the support of $P$ givewhich is the direct bound.

The test accepts $P$ when $D({\hat{P}}_n\Vert P)\le \delta$. Under $P$, the method of types givessoUnder $Q$, accepting $P$ requires a type in the closed set $\{R:D(R\Vert P)\le \delta \}$. ThereforewhereConsequently ${\mathrm{limsup}}_n{n}^{-1}{\log }_2{e}_i^{(n)}\le -D_i(\delta )$ for $i=1,2$. The first exponent is positive when $\delta >0$. Because relative entropy vanishes only when its arguments agree, the second is positive exactly while $Q$ lies outside the constraint set. Thus both are strictly positive for