Gallager expurgated exponent lower bound

For any two codewords $x^n,x^{\mathrm{\prime }n}$, if ML decoding selects the competitor when $x^n$ was sent, then $W^n(y^n\mid x^{\mathrm{\prime }n})\ge W^n(y^n\mid x^n)$. On that event $W^n(y^n\mid x^n)\le \sqrt{W^n(y^n\mid x^n)W^n(y^n\mid x^{\mathrm{\prime }n})}$; this also holds when the codewords coincide, in which case the pairwise sum is $1$. Summing over outputs and using a union bound over competitors gives message error at most $f_m:={\sum }_{j\mathrm{\ne }m}{B}^n(x_m^n,x_j^n)$, where $B^n(x^n,x^{\mathrm{\prime }n})={\prod }_{i}B(x_i,x_i^{\mathrm{\prime }})$.

Fix $r\in (0,1]$. If $r=1$, $(a+b{)}^r=a^r+b^r$. If $0<r<1$, then $u\mapsto u^{r-1}$ has derivative $(r-1)u^{r-2}<0$ on $(0,\mathrm{\infty })$ by [F4], so it is nonincreasing by [F5]. For $t>0$, put $g(t)=1+t^r-(1+t{)}^r$; [F4] gives $g^{\mathrm{\prime }}(t)=r(t^{r-1}-(1+t{)}^{r-1})\ge 0$. Also $t^r\to 0$ as $t\downarrow 0$: its derivative is positive, and for any $\eta >0$, $0<t<{\eta }^{1\mathrm{/}r}$ gives $t^r<\eta$ by [F4]–[F5]. Thus $g$ extends continuously to $g(0)=0$. By [F5] on $[0,\mathrm{\infty })$, $g(t)\ge 0$ for all $t\ge 0$. If $a>0$, scale with $t=b\mathrm{/}a$ and use [F4] to obtain $(a+b{)}^r\le a^r+b^r$; if $a=0$, equality holds, including $a=b=0$. Induction gives $({\sum }_j{a}_j{)}^r\le {\sum }_j{a}_j^r$ for every finite nonnegative family (the empty family gives $0=0$). Now draw $M^{\mathrm{\prime }}$ codewords independently from $P^n$ and take $r=1\mathrm{/}\rho$ for $\rho \ge 1$. The proved finite-sum inequality and step 1.1 yield $\mathbb{E}{f}_m^{1\mathrm{/}\rho }\le {\sum }_{j\mathrm{\ne }m}\mathbb{E}{B}^n(X_m^n,X_j^n{)}^{1\mathrm{/}\rho }=(M^{\mathrm{\prime }}-1){({\sum }_{x,x^{\mathrm{\prime }}}P(x)P(x^{\mathrm{\prime }})B(x,x^{\mathrm{\prime }}{)}^{1\mathrm{/}\rho })}^n\mathrm{.}$ The equality follows from independent coordinates, the product form of $B^n$, and the power laws in [F4].

Averaging [2.1] over messages and codebooks gives a codebook with $M^{\mathrm{\prime }-1}{\sum }_m{f}_m^{1\mathrm{/}\rho }\le (M^{\mathrm{\prime }}-1)z^n$, where $z={\sum }_{x,x^{\mathrm{\prime }}}P(x)P(x^{\mathrm{\prime }})B(x,x^{\mathrm{\prime }}{)}^{1\mathrm{/}\rho }$. At least $M^{\mathrm{\prime }}\mathrm{/}2$ messages satisfy $f_m^{1\mathrm{/}\rho }\le 2(M^{\mathrm{\prime }}-1)z^n$; otherwise their sum would exceed $M^{\mathrm{\prime }}(M^{\mathrm{\prime }}-1)z^n$. Restrict the code to $M^{\mathrm{\prime }}\mathrm{/}2$ such messages, using ML decoding among the retained words. Removing competitors cannot increase their ML error, so maximal error is at most $[2(M^{\mathrm{\prime }}-1)z^n{]}^{\rho }$.

Set $M^{\mathrm{\prime }}=2M_n$, retain exactly $M_n$ messages, and take $-n^{-1}\ln$ of the bound in step 3.1. Since $n^{-1}\ln (M^{\mathrm{\prime }}-1)\to R$, this gives $E_{\mathrm{m}\mathrm{a}\mathrm{x}}^{-}(R)\ge -\rho \ln z-\rho R=E_{0x}(\rho ,P)-\rho R$. Optimizing over $P$ and $\rho \ge 1$ proves the maximal-error bound. Average error is no larger than maximal error for the same code, so its liminf exponent satisfies the same lower bound.