First-order coding theorems separate possible from impossible rates. Strong converses and error exponents refine that boundary.
Strong converse
Definition. A channel has a strong converse if every code sequence with rate strictly above capacity has error probability tending to one, not merely bounded away from zero.
DMC strong converse
Theorem. Finite-alphabet discrete memoryless channels satisfy the strong converse: if \(\liminf n^{-1}\log M_n>C\), then the average probability of decoding error tends to one.
Error exponent
Definition. For rates below capacity, the reliability function is the best achievable exponential decay rate \[ E(R)=\sup\liminf_{n\to\infty}-\frac1n\log P_e^{(n)}. \] Random-coding and sphere-packing bounds give lower and upper bounds on \(E(R)\).
Change-of-measure idea
Proof. Strong converses compare the true channel output law with auxiliary output laws under which too many messages cannot be separated. Error exponents sharpen the same comparison by retaining exponential constants instead of only first-order rates.
Strong converse
Theorem. For a finite-alphabet DMC, if \[ \liminf_{n\to\infty}\frac1n\log M_n>C, \] then the average decoding error satisfies \(P_e^{(n)}\to1\).
Proof outline. Reduce a general code to a large constant-composition subcode, losing only polynomial size. For each codeword type \(P_X\), conditional type counting shows that a decoding region capturing nonvanishing channel probability must contain roughly \(e^{nH(Y\mid X)}\) outputs, while the aggregate output space of the corresponding types has size roughly \(e^{nH(Y)}\). Disjoint decoding regions therefore number at most \(e^{nI(P_X,W)+o(n)}\le e^{nC+o(n)}\). At a larger rate, the total correctly decoded mass vanishes.
Reliability function
Definition. The reliability function is \[ E(R)=\limsup_{n\to\infty} -\frac1n\log P_e^*(n,\lceil e^{nR}\rceil), \qquad0<R<C. \]
Random-coding and expurgated exponents give achievability lower bounds on \(E(R)\); sphere-packing gives a converse upper bound. Exact reliability is known only for special channels and rate regimes.
Random-coding exponent
Theorem. \[ E(R)\ge E_r(R)= \max_{P_X}\max_{0\le\rho\le1} \{E_0(\rho,P_X)-\rho R\}. \]
Near capacity, \(E_r(R)\) meets the sphere-packing exponent for many symmetric channels. At low rates, expurgating poor codewords can improve it.
Expurgated exponent
Theorem. Pairwise Bhattacharyya analysis and expurgation yield \[ E(R)\ge E_{\mathrm{ex}}(R), \] where one representation is \[ E_{\mathrm{ex}}(R)= \max_{P_X}\sup_{\rho\ge1} \{E_x(\rho,P_X)-\rho R\}, \] with \[ E_x(\rho,P_X)= -\rho\log\sum_{x,x'}P_X(x)P_X(x') \left[\sum_y\sqrt{W(y\mid x)W(y\mid x')}\right]^{1/\rho}. \]
Proof outline. Bound pairwise maximum-likelihood error by the Bhattacharyya coefficient. Average an appropriate power of the sum of pairwise coefficients over a random code. At least half the codewords have no more than twice the average pairwise burden; expurgate the rest and optimize the moment parameter \(\rho\).
Sphere-packing exponent
Theorem. A converse exponent is \[ E(R)\le E_{\mathrm{sp}}(R) =\max_{P_X} \min_{V:I(P_X,V)\le R} D(V\|W\mid P_X) \] under the appropriate constant-composition and rate conventions.
Proof outline. Replace the true channel \(W\) by an auxiliary channel \(V\) whose mutual information is below code rate. The strong converse under \(V\) forces nontrivial error. Change of measure from \(V^n\) to \(W^n\) costs conditional divergence \(D(V\|W\mid P_X)\), yielding a lower bound on \(W\)-error probability with the stated exponent. Optimize the auxiliary channel.
Above-capacity success exponent
Definition. For \(R>C\), the strong-converse exponent measures decay of correct probability: \[ E_{\mathrm{sc}}(R)= \liminf-\frac1n\log(1-P_e^*). \]
Arimoto and Dueck-Körner formulas characterize this exponent through Rényi-information quantities or auxiliary channels. Thus the transition at capacity has exponential structure on both sides: error decays below capacity, correct probability decays above it.
Moderate deviations
Theorem. If rates approach capacity as \(R_n=C-\rho_n\), where \(\rho_n\to0\) and \(\sqrt n\,\rho_n\to\infty\), then under regularity \[ -\log P_e^*(n,R_n) \sim\frac{n\rho_n^2}{2V}, \] with channel dispersion \(V\).
Moderate deviations interpolate between fixed-gap error exponents and the \(n^{-1/2}\) normal-approximation regime.
Zero-error capacity
Definition. Zero-error capacity requires disjoint output supports for every pair of codewords: \[ C_0=\sup_n\frac1n\log\alpha(G^{\boxtimes n}), \] where \(G\) is the confusability graph, \(\alpha\) its independence number, and \(\boxtimes\) the strong graph product.
Zero-error capacity can be strictly below Shannon capacity and is governed by graph structure rather than small-probability typicality. It illustrates how changing the error criterion changes the operational theorem.