IID Lossless Source Coding and the AEP

Define $Y_i={\mathrm{ı}}_p(X_i)$ when $X_i\in A_{+}$ and $Y_i=0$ otherwise. This is the same finite-valued measurable function of every $X_i$, so its range is finite. Take arbitrary distinct indices $i_1,\dots ,i_m$ and Borel sets $B_1,\dots ,B_m$. Then ${\bigcap }_{j=1}^m\{Y_{i_j}\in B_j\}={\bigcap }_{j=1}^m\{X_{i_j}\in {\mathrm{ı}}_p^{-1}(B_j)\}$; mutual independence in [F6] gives probability ${\prod }_{j=1}^m\mathbb{P}(X_{i_j}\in {\mathrm{ı}}_p^{-1}(B_j))$, and the common law $p$ makes every $Y_i$ have the same law. Thus the $Y_i$ are IID.

Since $\mathbb{P}(X_i=a)=p(a)$, zero-mass symbols contribute nothing, and finite summation using [F4] gives $\mathbb{E}[Y_i]=H(p)$; the definition of $V(p)$ in [F2] gives $\mathrm{Var}(Y_i)=V(p)$. Finite range gives square integrability.

For each fixed $n$, each event $\{X_i\mathrm{\notin }{A}_{+}\}$ has probability zero because its probability is ${\sum }_{a\mathrm{\notin }{A}_{+}}p(a)=0$; the finite union also has probability zero. On its complement, [F1] and [F5] give $I_n(X^n)=n^{-1}{\sum }_{i=1}^n{Y}_i$. Applying [F7] with mean $H(p)$ and variance $V(p)$ proves the displayed tail bound. Its strict-tail version and [F8] give convergence in probability.

If $x^n\in T_n(\epsilon )$, [F1] gives $p^n(x^n)=e^{-n{I}_n(x^n)}\ge e^{-n(H(p)+\epsilon )}$. Summing these probabilities over $T_n(\epsilon )$ and using total mass one yields $\mathrm{\mid }{T}_n(\epsilon )\mathrm{\mid }{e}^{-n(H(p)+\epsilon )}\le 1$, proving the upper bound.

The other side of [F1] gives $p^n(x^n)\le e^{-n(H(p)-\epsilon )}$ for each typical sequence. Hence $\mathbb{P}(X^n\in T_n(\epsilon ))\le \mathrm{\mid }{T}_n(\epsilon )\mathrm{\mid }{e}^{-n(H(p)-\epsilon )}$; rearranging and using $\mathbb{P}(X^n\in T_n(\epsilon ))=1-{\delta }_n$ proves the lower bound.

The complement of the typical set is contained in $\{\mathrm{\mid }{I}_n(X^n)-H(p)\mathrm{\mid }\ge \epsilon \}$, so [F2] bounds ${\delta }_n$ by $V(p)\mathrm{/}(n{\epsilon }^2)$. This tends to zero, including when $V(p)=0$.

Let ${\epsilon }_n=n^{-1\mathrm{/}4}$ and $T_n=T_n({\epsilon }_n)$. Put $M_n=\mathrm{\mid }{T}_n\mathrm{\mid }+1$ and $k_n=\lceil {\log }_2{M}_n\rceil$. Fix $a_0\in A$, possible since $A$ is nonempty, and assign distinct binary strings of length $k_n$ to the words in $T_n$ plus one unused string. Encode each typical word by its assigned string and every other word by the unused string; decode assigned strings to their typical words and all other strings to $a_0^n$. This defines maps on all of $A^n$, and every typical word is decoded correctly.

For any length-$n$ code, let $C_n=\{x^n\in A^n:g_n(f_n(x^n))=x^n\}$ be its correctly decoded set. Each binary message has only one decoder output, so $\mathrm{\mid }{C}_n\mathrm{\mid }\le 2^{k_n}$. For any $\gamma >0$, every $x^n\in C_n\cap T_n(\gamma )$ has $p^n(x^n)\le e^{-n(H(p)-\gamma )}$. Therefore $1-e_n=\mathbb{P}(X^n\in C_n)\le {\delta }_n(\gamma )+\mathrm{\mid }{C}_n\mathrm{\mid }{e}^{-n(H(p)-\gamma )}\le {\delta }_n(\gamma )+e^{n(R_n-H(p)+\gamma )}\mathrm{.}$ Here [F1] supplies the number of messages, [F2] the source law, [F3] the product law, [F4]–[F6] the log, entropy and typical-set conventions, and [F7] the error-tail notation.

The error is at most ${\delta }_n({\epsilon }_n)\le V(p)\mathrm{/}(n{\epsilon }_n^2)=V(p)\mathrm{/}\sqrt{n}$ by [F7]. For each $a$ with $p(a)>0$, $p(a)\le 1$, and [F4] gives $\ln p(a)\le \ln 1=0$; hence each summand $-p(a)\ln p(a)$ in [F5] is nonnegative and $H(p)\ge 0$. Thus $M_n\le e^{n(H(p)+{\epsilon }_n)}+1\le 2e^{n(H(p)+{\epsilon }_n)}$. Since $k_n=\lceil {\log }_2{M}_n\rceil$, $k_n\ln 2\le \ln M_n+\ln 2$, so $R_n\le H(p)+n^{-1\mathrm{/}4}+2\ln 2\mathrm{/}n$. These bounds prove the achievability claims.

Suppose $\rho :=\mathrm{lim\hspace{0.17em}sup}{R}_n<H(p)$. Since $\ln 2>\ln 1=0$ by [F4] and $k_n\ge 0$ by [F1], all rates are nonnegative. The finite sum in [F5] has finitely many finite terms, so $H(p)$ and then $\rho$ are finite reals. Choose $\gamma =(H(p)-\rho )\mathrm{/}4>0$. Eventually $R_n\le \rho +\gamma =H(p)-3\gamma$. Then step 1.2 gives $1-e_n\le {\delta }_n(\gamma )+e^{-2n\gamma }\to 0$ by [F7], so $e_n\to 1$.

Suppose instead that $e_n\to 0$ but $L:=\mathrm{lim\hspace{0.17em}inf}{R}_n<H(p)$. Since $\ln 2>\ln 1=0$ by [F4] and $k_n\ge 0$ by [F1], all rates are nonnegative. The finite sum in [F5] has finitely many finite terms, so $H(p)$ and $L$ are finite reals. Take $\gamma =(H(p)-L)\mathrm{/}4>0$. Infinitely many $n$ satisfy $R_n\le L+\gamma =H(p)-3\gamma$. Along those indices, step 1.2 and [F7] give $1-e_n\le {\delta }_n(\gamma )+e^{-2n\gamma }\to 0$, contradicting $e_n\to 0$. Hence $\mathrm{lim\hspace{0.17em}inf}{R}_n\ge H(p)$.