Gallager random-coding exponent lower bound

Fix $0<\rho \le 1$, an input law $P$, and an $M$-word codebook drawn independently from $P^n$. Use maximum-likelihood decoding with the lowest-index tie rule. If message $m$ is sent and $y^n$ is received with $W^n(y^n\mid x_m^n)>0$, an error implies some competitor has likelihood at least the true likelihood. Hence its error indicator is at most ${\left({\sum }_{j\mathrm{\ne }m}{\left[\frac{W^n(y^n\mid x_j^n)}{W^n(y^n\mid x_m^n)}\right]}^{1\mathrm{/}(1+\rho )}\right)}^{\rho },$ which is at least one on every error event; outputs of zero true likelihood carry no channel mass.

For fixed $P$, write $A_y(\rho )={\sum }_{x}P(x)W(y\mid x{)}^{1\mathrm{/}(1+\rho )}$ and $S(\rho )={\sum }_y{A}_y(\rho {)}^{1+\rho }$. If $W(y\mid x)>0$, [F7]–[F8] and the chain rule give ${\frac{d}{d\rho }W(y\mid x{)}^{1\mathrm{/}(1+\rho )}\mid }_{\rho =0}=-W(y\mid x)\ln W(y\mid x)$; if $W(y\mid x)=0$, that term is identically zero. Thus, for $q_y=A_y(0)=(PW)(y)>0$, $A_y^{\mathrm{\prime }}(0)=-{\sum }_{x:W(y\mid x)>0}P(x)W(y\mid x)\ln W(y\mid x)\mathrm{.}$ On a neighborhood of $0$ where $A_y(\rho )>0$, write $A_y(\rho {)}^{1+\rho }=\exp ((1+\rho )\ln A_y(\rho ))$. By [F7]–[F8] and the product and chain rules, its derivative at zero is $q_y\ln q_y+A_y^{\mathrm{\prime }}(0)$. If $q_y=0$, every $P(x)W(y\mid x)=0$, so $A_y(\rho )=0$ for all $\rho \ge 0$ and its outer term vanishes identically. Summing the finite terms gives $S^{\mathrm{\prime }}(0)={\sum }_{y:q_y>0}{q}_y\ln q_y-{\sum }_{x,y:P(x)W(y\mid x)>0}P(x)W(y\mid x)\ln W(y\mid x)=-I(P,W),$ because [F5] expands $I(P,W)={\sum }_{x,y:PW>0}P(x)W(y\mid x)\ln \frac{W(y\mid x)}{q_y}$. Since $S(0)=1$ and $E_0(\rho ,P)=-\ln S(\rho )$, the right derivative is ${\mathrm{\partial }}_{\rho }{E}_0(0,P)=I(P,W)$.

Fix $0<\rho \le 1$. By [F8], the function $h(t)=-t^{\rho }$ on $(0,\mathrm{\infty })$ has $h^{\mathrm{\prime }\mathrm{\prime }}(t)=\rho (1-\rho )t^{\rho -2}\ge 0$, so [F10] makes it convex there (for $\rho =1$ it is affine). The positive derivative $\rho t^{\rho -1}$ and [F11] make $t^{\rho }$ increasing. Given $\eta >0$, put $\delta ={\eta }^{1\mathrm{/}\rho }$; if $0<t<\delta$, then $0<t^{\rho }<{\delta }^{\rho }=\eta$ by [F11]. Thus $t^{\rho }$ extends continuously to zero with value zero. For nonnegative $x,y$ and a weight $\lambda \in [0,1]$, apply the convexity inequality for $h$ to $x+u,y+u>0$ and let $u\downarrow 0$; continuity extends it to $[0,\mathrm{\infty })$. Applying finite convex Jensen [F3] to this $h$ and the values of any finite nonnegative random variable $Z$ gives $-(\mathbb{E}Z{)}^{\rho }\le -\mathbb{E}{Z}^{\rho }$, or $\mathbb{E}{Z}^{\rho }\le (\mathbb{E}Z{)}^{\rho }$. This includes $\mathbb{E}Z=0$ and $\rho =1$ without a zero-to-zero power convention.

Conditional on $x_m^n,y^n$, the power Jensen inequality from step 1.3 bounds the expected $\rho$-power by the $\rho$-power of its mean. Independence of each competitor gives that mean as $(M-1)\frac{A_n(y^n)}{W^n(y^n\mid x_m^n{)}^{1\mathrm{/}(1+\rho )}},A_n(y^n):={\sum }_{x^n}{P}^n(x^n)W^n(y^n\mid x^n{)}^{1\mathrm{/}(1+\rho )}\mathrm{.}$ Multiplication by the true likelihood changes its power to $1-\rho \mathrm{/}(1+\rho )=1\mathrm{/}(1+\rho )$. Averaging over the transmitted word and summing over outputs therefore bounds ensemble average error by $(M-1{)}^{\rho }{\sum }_{y^n}{A}_n(y^n{)}^{1+\rho }\mathrm{.}$

The product law in [F1] makes $A_n(y^n)={\prod }_{i=1}^n{\sum }_{x}P(x)W(y_i\mid x{)}^{1\mathrm{/}(1+\rho )}$. Thus the sum in step 2.1 factors into the $n$th power of the single-letter sum defining $E_0(\rho ,P)$ in [F2]. Some deterministic codebook has average error at most its ensemble mean, so for each $n$ a code exists with ${ϵ}_{\mathrm{a}\mathrm{v}}\le \exp \{-n[E_0(\rho ,P)-\rho n^{-1}\ln (M-1)]\}\mathrm{.}$

With $M_n=\lceil e^{nR}\rceil$, one has $n^{-1}\ln (M_n-1)\to R$. Taking the liminf exponent in step 3.1 and optimizing over $P$ and $0<\rho \le 1$ gives the corresponding positive-parameter supremum. For a capacity-achieving $P^{\ast }$ from [F6], each $A_y(\rho )$ tends to $q_y=(P^{\ast }W)(y)$ as $\rho \downarrow 0$. If $q_y>0$, then $A_y(\rho {)}^{1+\rho }=\exp ((1+\rho )\ln A_y(\rho ))\to q_y$; if $q_y=0$, all $P^{\ast }(x)W(y\mid x)=0$ and that term is identically zero. Hence $S(\rho )\to {\sum }_y{q}_y=1$ and $E_0(\rho ,P^{\ast })=-\ln S(\rho )\to 0$ by [F9]. Since $E_0(\rho )\ge E_0(\rho ,P^{\ast })$, the positive-parameter supremum is at least ${\lim }_{\rho \downarrow 0}(E_0(\rho ,P^{\ast })-\rho R)=0$. The added endpoint $\rho =0$ has value zero, so it does not change the supremum, which is $E_r(R)$.

Apply the same bound at size $2M_n$ and then [F4]. The retained code has at least $M_n$ messages, so selecting exactly $M_n$ messages leaves maximal error at most twice the old average error. The factor two and the rate difference $n^{-1}\ln (2M_n)-R\to 0$ do not change the liminf exponent. Hence $E_{\mathrm{m}\mathrm{a}\mathrm{x}}^{-}(R)\ge E_r(R)$.

If $R<C(W)$, choose a maximizing $P^{\ast }$ by [F6]. Step 1.2 gives $E_0(\rho ,P^{\ast })-\rho R=\rho (C(W)-R)+o(\rho )>0$ for sufficiently small $\rho >0$. The supremum defining $E_r(R)$ is therefore positive.