AEP criterion for fixed-rate lossless coding

If $h<0$, then the nonnegative variable $I_n(X^n)\mathrm{/}n$ stays at distance at least $-h$ from $h$, contradicting convergence in probability; hence $h\ge 0$. Let $R>h$ and choose $ϵ>0$ with $h+ϵ<R$. Define $T_n=\{x:p_n(x)>0,I_n(x)\le n(h+ϵ)\}$. On $T_n$, each word has probability at least $2^{-n(h+ϵ)}$, so $\mathrm{\mid }{T}_n\mathrm{\mid }\le 2^{n(h+ϵ)}$. The AEP gives $P(X^n\in T_n)\to 1$.

For all sufficiently large $n$, $\mathrm{\mid }{T}_n\mathrm{\mid }\le 2^{\lfloor nR\rfloor }$, since $R-h-ϵ>0$. Fix an enumeration of the finite alphabet $\mathcal{A}$ once, and let $a_0$ be its first symbol. For each such $n$, order $T_n$ lexicographically, take $M_n=\{0,1{\}}^{\lfloor nR\rfloor }$ in lexicographic order, and map the $j$th typical block to the $j$th binary word. Define $e_n$ by this assignment on $T_n$ and by $e_n(x)=0^{\lfloor nR\rfloor }$ otherwise. Define $d_n$ to return each typical block on its assigned message and $a_0^n$ on all remaining messages. This is a rate-$R$ code in the sense of [F2], and every block in $T_n$ is decoded correctly. Its error is at most $P(X^n\mathrm{\notin }{T}_n)\to 0$. For the finitely many earlier $n$, take $e_n$ constant at the all-zero message and $d_n$ constant at $a_0^n$.

Let $0\le R<h$ and choose $ϵ>0$ with $R+ϵ<h$. For any rate-$R$ code, its success set $S_n$ has at most $2^{\lfloor nR\rfloor }$ words by [F2]. Split it according to whether $I_n(x)>n(R+ϵ)$. The probability of successful words in that part is at most $2^{nR}{2}^{-n(R+ϵ)}=2^{-nϵ}$, while the other part has total probability tending to zero by the AEP. Thus success probability tends to zero. At $R=h$ neither conclusion is asserted.