= 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\Vert P),
$$
meaning that the best fixed-rate codes satisfy
$$
\lim_{n\to\infty}-\frac1n\log_2P_e^{(n)}=E(R)
$$
at continuity points of the exponent.
For the direct part, let $m=|A|$ and
$$
\eta_n=\frac{m\log_2(n+1)}n.
$$
Encode every sequence whose <type (information theory)> $Q$ satisfies $H(Q)\leq R-\eta_n$. The <method of types> bounds the number of such sequences by
$$
(n+1)^m2^{n(R-\eta_n)}=2^{nR},
$$
so they fit into a rate-$R$ codebook. The error probability obeys
$$
\begin{aligned}
P_e^{(n)}
&\leq\sum_{Q:H(Q)>R-\eta_n}P^{\otimes n}(T(Q))\\
&\leq(n+1)^m
2^{-n\min_{Q:H(Q)>R-\eta_n}D(Q\Vert P)}.
\end{aligned}
$$
Compactness of the probability simplex and continuity of entropy and relative entropy on the support of $P$ give
$$
\liminf_{n\to\infty}-\frac1n\log_2P_e^{(n)}
\geq\min_{Q:H(Q)\geq R}D(Q\Vert P)=E(R),
$$
which is the direct bound.
Back to article page
