Nondegenerate normal approximation for finite unconstrained DMCs

Choose any CAID and let $Q^{\ast }$ be its output law. By [F3], every row is supported on $Q^{\ast }$ and has divergence $d_x:=D(W_x\mathrm{\parallel }{Q}^{\ast })\le C(W)$. For every CAID $P$, [F5] gives $\mathbb{E}[{\mathrm{ı}}_P(X;Y)\mid X=x]=C(W)$ on each positive-mass input and $\mathrm{Var}({\mathrm{ı}}_P(X;Y))=V(P,W)$.

By [F13] the input simplex is compact. Expanding the finite KL definition [F14] gives $I(P,W)=H(PW)-{\sum }_{x}P(x)H(W_x)$; by [F11], $t\ln t\to 0$ at zero, so this function is continuous. Since $C(W)={\max }_{P}I(P,W)$ by [F2], its maximizing level set $\mathrm{\Pi }(W)$ is closed and therefore compact; [F2], [F4] supply a minimum-dispersion CAID. Since $Q^{\ast }$ is positive on every globally reachable output, choose $U=\{P\in {\mathrm{\Delta }}_{\mathcal{X}}:{\mathrm{dist}}_2(P,\mathrm{\Pi }(W))<\delta \}$ with compact closure in the input simplex and with every $(PW)(y)$ on that support bounded below by a positive constant on $\bar{U}$. On the support of each row define ${\mathrm{\ell }}_P(x;y):=\ln [W(y\mid x)\mathrm{/}(PW)(y)]$; it is finite on $U$ and agrees with ${\mathrm{ı}}_P(x;y)$ whenever $P(x)>0$. Define $T(P,W):={\sum }_{x:P(x)>0}P(x){\mathbb{E}}_{W_x}\mathrm{\mid }{\mathrm{\ell }}_P(x;Y)-D(W_x\mathrm{\parallel }PW){\mathrm{\mid }}^3$, omitting zero-weight rows. The local extensions of $V$ and $T$ are respectively ${\sum }_{x}P(x){\mathrm{Var}}_{W_x}{\mathrm{\ell }}_P(x;Y)$ and the same third-moment sum over all $x$; they agree with the support-restricted formulas because zero-weight rows contribute zero. They are $C^1$: the logarithm arguments stay positive on a neighborhood of $\bar{U}$, and $u\mapsto \mathrm{\mid }u{\mathrm{\mid }}^3$ has continuous derivative $3u\mathrm{\mid }u\mathrm{\mid }$. Their first derivatives are bounded on compact $\bar{U}$. Since $V\ge V_{\min }>0$ on $\mathrm{\Pi }(W)$, shrink $\delta$ so that $V\ge v_0>0$ on $\bar{U}$, and let $T_0$ bound $T$ there. The segment from any $P\in U$ to a nearest $P_0\in \mathrm{\Pi }(W)$ stays in $U$; the mean-value theorem then gives $\mathrm{\mid }\sqrt{V(P,W)}-\sqrt{V(P_0,W)}\mathrm{\mid }\le L\mathrm{\parallel }P-P_0{\mathrm{\parallel }}_2$ for one finite $L$.

There is also a global constant $B<\mathrm{\infty }$ with $V(P,W)\le B$ for every input law. Indeed, let $w_0$ be the least positive transition probability of $W$. If $P(x)>0$ and $W(y\mid x)>0$, then $(PW)(y)\ge P(x)W(y\mid x)$, so $\mathrm{\mid }{\mathrm{ı}}_P(x;y)\mathrm{\mid }\le \mathrm{\mid }\ln w_0\mathrm{\mid }+\mathrm{\mid }\ln P(x)\mathrm{\mid }$. The function $t(1+\mathrm{\mid }\ln t\mathrm{\mid }{)}^2$ extends continuously to zero and is bounded on $[0,1]$; summing the resulting finite bound over $x$ gives $\mathbb{E}{\mathrm{ı}}_P^2\le B$ and hence $V(P,W)\le B$.

Fix a code whose every codeword has type $P$ and let $Q_n=(PW{)}^n$. For message $m$ with codeword $x_m^n$, put $L_m(y^n)=\ln [W^n(y^n\mid x_m^n)\mathrm{/}{Q}_n(y^n)]$ on its charged support. Every codeword of type $P$ gives the same distribution of $L_m$ under its channel law, with mean $nI(P,W)$ and variance $nV(P,W)$; the summands are independent and row counts are $nP(x)$. For any $\gamma >0$, split each decoder region at $t=\ln M-\gamma$. On $L_m\le t$, $W^n(y^n\mid x_m^n)\le M{e}^{-\gamma }{Q}_n(y^n)$. Averaging over messages and using disjoint decoder regions gives $1-e_{\mathrm{a}\mathrm{v}}\le \mathrm{Pr}\{L>\ln M-\gamma \}+e^{-\gamma },F_L(\ln M-\gamma )\le e_{\mathrm{a}\mathrm{v}}+e^{-\gamma }\mathrm{.}$

For $P\in U$, Berry–Esseen [F7] applied to the centered independent row log-likelihood terms in step 1.4 gives a uniform bound ${\sup }_z\mathrm{\mid }{F}_L(nI(P,W)+\sqrt{nV(P,W)}z)-\mathrm{\Phi }(z)\mathrm{\mid }\le B_0\mathrm{/}\sqrt{n},$ where $B_0=1088T_0\mathrm{/}{v}_0^{3\mathrm{/}2}$. If $e_{\mathrm{a}\mathrm{v}}\le ϵ+n^{-1\mathrm{/}2}$ and $\gamma =\frac{1}{2}\ln n$, step 1.4 yields $\mathrm{\Phi }\text{\hspace{0.17em}⁣}\left(\frac{\ln M-\gamma -nI(P,W)}{\sqrt{nV(P,W)}}\right)\le ϵ+(B_0+2)n^{-1\mathrm{/}2}\mathrm{.}$ Since $ϵ$ is fixed in $(0,1)$, choose a compact interval about $z_{ϵ}$ on which the positive density $\phi$ has lower bound $m>0$. The mean-value theorem [F12] gives $\mathrm{\mid }\mathrm{\Phi }(u)-\mathrm{\Phi }(v)\mathrm{\mid }\ge m\mathrm{\mid }u-v\mathrm{\mid }$ there, so the inverse is locally Lipschitz at $ϵ$. Hence, uniformly for such types, $\ln M\le nI(P,W)+\sqrt{nV(P,W)}{z}_{ϵ}+\frac{1}{2}\ln n+O(1),z_{ϵ}:={\mathrm{\Phi }}^{-1}(ϵ)\mathrm{.}$

Fix $\delta >0$ so that $U$ contains the $\delta$-neighborhood of $\mathrm{\Pi }(W)$. On the compact set $\mathrm{dist}(P,\mathrm{\Pi }(W))\ge \delta$, continuity and the definition of $\mathrm{\Pi }(W)$ give $I(P,W)\le C-\eta$ for some $\eta >0$. If a constant-composition code there had $\ln M-\gamma >nI(P,W)+K\sqrt{n}$, then on $L>nI(P,W)+K\sqrt{n}$, the squared centered deviation exceeds $K^{2}n$, so its indicator is at most $(L-nI(P,W){)}^2\mathrm{/}(K^{2}n)$. Taking expectations and using step 1.3 gives $F_L(\ln M-\gamma )\ge 1-B\mathrm{/}{K}^2$. Choose $K$ with $1-B\mathrm{/}{K}^2>ϵ$; this contradicts step 1.4 and $e_{\mathrm{a}\mathrm{v}}\le ϵ+n^{-1\mathrm{/}2}$ for large $n$. Therefore $\ln M\le n(C-\eta )+K\sqrt{n}+\frac{1}{2}\ln n$, which is below the claimed normal upper bound for all sufficiently large $n$.

Let $P^{\ast }\in \mathrm{\Pi }(W)$ attain $V_{\min }$. By [F5], under $P^{\ast }W$ the information density has mean $C$ and variance $V_{\min }$; its third absolute centered moment $T^{\ast }<\mathrm{\infty }$. Apply [F8] to $P^{\ast n}$. For $\gamma =\frac{1}{2}\ln n$, the DT expectation is at most $\mathrm{Pr}\{S_n\le \ln ((M-1)\mathrm{/}2)+\gamma \}+e^{-\gamma },$ by splitting at the displayed threshold. Berry–Esseen [F7] bounds this by $\mathrm{\Phi }((t-nC)\mathrm{/}\sqrt{n{V}_{\min }})+1088T^{\ast }\mathrm{/}(V_{\min }^{}\sqrt{n})+n^{-1\mathrm{/}2}$, where $t=\ln ((M-1)\mathrm{/}2)+\gamma$.

Put $a=-z_{ϵ}>0$ and $d={\mathrm{dist}}_2(P,\mathrm{\Pi }(W))$. For $P\in U$, choose a nearest $P_0\in \mathrm{\Pi }(W)$, so $V(P_0,W)\ge V_{\min }$. By [F6] and step 1.2, $nI(P,W)-a\sqrt{nV(P,W)}\le nC-a\sqrt{n{V}_{\min }}-n\alpha d^2+aL\sqrt{n}d\le nC-a\sqrt{n{V}_{\min }}+\frac{a^2{L}^2}{4\alpha }\mathrm{.}$ Together with step 2.1 this gives the desired $nC+\sqrt{n{V}_{\min }}{z}_{ϵ}+O(\ln n)$ upper bound for nearby constant-composition codes.

Set $u_n=ϵ-(1088T^{\ast }\mathrm{/}{V}_{\min }^{}+2)n^{-1\mathrm{/}2}$ and $t_n=nC+\sqrt{n{V}_{\min }}{\mathrm{\Phi }}^{-1}(u_n)$, for large $n$ with $u_n>0$. We have $C>0$: if $C=0$, every point-mass input is a CAID and has zero dispersion, contradicting $V_{\min }>0$. Choose $M=1+\lfloor 2e^{t_n-\gamma }\rfloor$, which is at least two for large $n$ and satisfies $t\le t_n$ and $\ln M\ge t_n-\gamma -O(1)$. Step 2.3 and [F7] give a deterministic code with average error at most $ϵ-n^{-1\mathrm{/}2}$ and $\ln M\ge nC+\sqrt{n{V}_{\min }}{z}_{ϵ}-O(\ln n),$ using local Lipschitz continuity of ${\mathrm{\Phi }}^{-1}$ at $ϵ$ from [F12].

For an arbitrary code of size $M$ with individual errors $e_m\ge 0$ and average error at most $ϵ$, put $\tau =ϵ+n^{-1\mathrm{/}2}$ and let $b$ count the messages with $e_m>\tau$. If $b>0$, then $b\tau <{\sum }_{e_m>\tau }{e}_m\le {\sum }_m{e}_m\le Mϵ$, so the retained count $g=M-b$ satisfies $g>M(1-ϵ\mathrm{/}\tau )=M\mathrm{/}(1+ϵ\sqrt{n})$. If $b=0$, then $g=M$ satisfies the same weak lower bound. Hence in all cases $g\ge \lceil M\mathrm{/}(1+ϵ\sqrt{n})\rceil \ge 1$, and every retained message has error at most $\tau$. Restrict the decoder to the retained set, mapping removed outputs to a fixed retained label; no retained message's error increases. Among at most $K=(n+1{)}^{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}$ input types, one type subcode has at least $\lceil g\mathrm{/}K\rceil$ messages, hence at least $M\mathrm{/}[(1+ϵ\sqrt{n})K]$. Its logarithmic size loss is therefore at most $\ln (1+ϵ\sqrt{n})+\mathrm{\mid }\mathcal{X}\mathrm{\mid }\ln (n+1)=O(\ln n)$ and its average error is at most $ϵ+n^{-1\mathrm{/}2}$. Applying steps 2.1, 2.2, and 3.1 to this type subcode gives $\ln M\le nC+\sqrt{n{V}_{\min }}{z}_{ϵ}+O(\ln n)\mathrm{.}$

A code with maximal error at most $ϵ$ also has average error at most $ϵ$, so step 4.1 bounds maximal-error code sizes as well. The largest code sizes are finite: average success is at most $\mathrm{\mid }\mathcal{Y}{\mathrm{\mid }}^n\mathrm{/}M$, since each output is decoded as only one message and contributes at most one to the sum of message success probabilities. Thus $M\le \mathrm{\mid }\mathcal{Y}{\mathrm{\mid }}^n\mathrm{/}(1-ϵ)$ for either criterion.

For all sufficiently large $n$ with $n^{-1\mathrm{/}2}<ϵ$, let $M$ be the size of the code of step 3.2 and let $b$ count its messages with individual error $e_m>ϵ$. If $b>0$, then $bϵ<{\sum }_{e_m>ϵ}{e}_m\le {\sum }_m{e}_m\le M(ϵ-n^{-1\mathrm{/}2})$, so its retained count $g=M-b$ satisfies $g>M\mathrm{/}(ϵ\sqrt{n})$. If $b=0$, $g=M\ge M\mathrm{/}(ϵ\sqrt{n})$ because $ϵ\sqrt{n}>1$. Therefore $g\ge \lceil M\mathrm{/}(ϵ\sqrt{n})\rceil \ge 1$, and every retained message has error at most $ϵ$. Restricting the decoder as in step 4.1 does not increase those errors. The resulting code has maximal error at most $ϵ$ and log size at least $\ln M-\ln (ϵ\sqrt{n})$, so it loses at most $\frac{1}{2}\ln n+\ln ϵ=\frac{1}{2}\ln n+O(1)$. Combining the average achievability from step 3.2 and the maximal construction above with the average and maximal converses from steps 4.1 and 5.1 proves both equalities in the Statement.