Fixed-rate source-coding error exponent

Let $Q$ be a nonuniform probability mass function with positive mass on an alphabet of size $m\ge 2$. For independent and identically distributed source words, let ${ϵ}_n^{\ast }(R)$ be the smallest reconstruction-error probability using at most $\lfloor 2^{nR}\rfloor$ messages. In the nontrivial interval $H_2(Q)<R<{\log }_{2}m$,Both Shannon entropy and Kullback-Leibler divergence here use base-two logarithms.

The method of types gives a direct proof.^[ref] Encode all words of types with Shannon entropy at most $R-\delta$; their total cardinality fits the budget for large $n$, since there are only polynomially many types. Their complement has the relative entropy exponent above as $\delta \downarrow 0$. Conversely a type class of Shannon entropy greater than $R$ has exponentially more words than the code can reconstruct. Its words are equiprobable, so almost all its probability is lost. Minimizing that relative entropy gives the matching converse.

At $R\ge {\log }_{2}m$ every possible word fits, so the error is zero and its exponent is infinite. Substituting that boundary rate into the displayed minimum would incorrectly give a finite answer. If using natural logarithms for the error exponent, multiply the base-two value by $\log 2$.