Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite-Blocklength Bounds and Reliability

1 · Prerequisites

2 · Summary

This page treats finite-alphabet, unconstrained, no-feedback discrete memoryless channels using natural logarithms and deterministic fixed-length encoders and decoders. It develops one-shot dependence-testing achievability and meta-converse bounds, Gallager random-coding and expurgated lower bounds, and a sphere-packing converse only above its stated finite-divergence strict-feasibility threshold. Reliability exponents are defined with separate liminf and limsup conventions; an exact general low-rate reliability formula is not asserted. Expected ensemble-average error does not by itself control maximal error; the explicit expurgation arguments state their rate and error costs.

The normal-approximation theorem is limited to a fixed $0 < ϵ < 1 / 2$ and a channel with $V_{\min} > 0$ . Its proof supplies a finite Pinsker bound, a finite affine-slice error estimate, and a uniform Berry–Esseen step before the type converse. The page makes no cost-constrained, feedback, zero-dispersion, $ϵ \geq 1 / 2$ , success-exponent, or third-order claim. The sphere-packing converse states its Axiom of Choice and Countable Choice assumptions where it uses Euclidean separation.

\begin{tikzpicture}[>=stealth]
  \node (m) at (0,0) {$J\in[M]$};
  \node[draw] (enc) at (2,0) {$e:[M]\to\mathcal X^n$};
  \node (x) at (4.5,0) {$X^n=e(J)$};
  \node[draw] (ch) at (6.7,0) {$W^n$};
  \node (y) at (9,0) {$Y^n$};
  \node[draw] (dec) at (11,0) {$d:\mathcal Y^n\to[M]$};
  \node (mhat) at (13.2,0) {$\widehat J$};
  \draw[->] (m) -- (enc);
  \draw[->] (enc) -- (x);
  \draw[->] (x) -- (ch);
  \draw[->] (ch) -- (y);
  \draw[->] (y) -- (dec);
  \draw[->] (dec) -- (mhat);
\end{tikzpicture}

The boxes are deterministic maps and $W^{n}$ is the memoryless product channel. This diagram records the fixed-length code interface; the proofs establish the stated error bounds directly and do not rely on the diagram.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

Error bound for a finite simplex and affine slice

Statement

Let $d \geq 1$ , let $Δ_{d} = {p \in R^{d} : p_{i} \geq 0, \sum_{i} p_{i} = 1}$ , let $M : R^{d} \to R^{r}$ be linear, and let $F = {q \in Δ_{d} : M q = b}$ be nonempty. There is a finite $H$ such that ${dist}_{2} (p, F) \leq H ∥ M p - b ∥_{2} (p \in Δ_{d}) .$

Facts & Assumptions

Given: The finite-dimensional simplex, linear map, and nonempty affine slice in the Statement.

[F1]

Every point has a unique nearest point in a nonempty closed Euclidean convex set: every point of Euclidean space has a unique nearest point in a nonempty closed convex set.

[F2]

Metric projection onto a closed convex set satisfies the variational inequality: if $q$ is the nearest point in a closed convex set to $p$ , then $⟨ p - q, z - q ⟩ \leq 0$ for every point $z$ in that set.

[F3]

For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: closed bounded subsets of finite-dimensional Euclidean space are compact, and continuous real functions attain minima on nonempty compact sets.

Proof

1.1givenalgebra

For each support set $J \subseteq {1, \dots, d}$ realized as $J = supp q$ by some $q \in F$ , define $C_{J} = {v : \sum_{i} v_{i} = 0, v_{i} \geq 0 (i \notin J), ⟨ v, w ⟩ \leq 0 for every w with \sum_{i} w_{i} = 0, M w = 0, w_{i} \geq 0 (i \notin J)} .$ This is a closed cone, being an intersection of closed linear constraints and closed half-spaces. If $v \in C_{J}$ and $M v = 0$ , then $v$ is an allowed $w$ in its defining inequality, hence $∥ v ∥_{2}^{2} \leq 0$ and $v = 0$ .

1.2F1givenconstruct

The set $F = Δ_{d} \cap M^{- 1} {b}$ is nonempty, closed, and convex: in coordinates it is given by finitely many closed linear inequalities and affine equations. Thus [F1] applies. Suppose $p \notin F$ and let $q$ be its nearest point in $F$ . Put $J = supp q$ and $v = (p - q) / ∥ p - q ∥_{2}$ . Then $\sum_{i} v_{i} = 0$ and $v_{i} \geq 0$ outside $J$ , because $p_{i} \geq 0 = q_{i}$ there.

2.1F1F2F3step 1.1algebra

For each realized $J$ , the set $C_{J} \cap {v : ∥ v ∥_{2} = 1}$ is compact by [F3]. If nonempty, the continuous function $v \mapsto ∥ M v ∥_{2}$ has a positive minimum $c_{J}$ : a zero would contradict step 1.1. There are finitely many $J$ , so the minimum $c$ of these positive $c_{J}$ is positive whenever any such unit section is nonempty. If all are empty, suppose $p \notin F$ and take its nearest point $q \in F$ by [F1]. With $J = supp q$ and $v = (p - q) / ∥ p - q ∥_{2}$ , every vector $w$ in the tangent conditions defining $C_{J}$ has $q + t w \in F$ for small $t > 0$ . [F2] then gives $⟨ v, w ⟩ \leq 0$ , so $v \in C_{J}$ and $∥ v ∥_{2} = 1$ , a contradiction. Hence $F = Δ_{d}$ and the claim is immediate.

2.2F2step 1.2givenalgebra

If $w$ satisfies the linear and sign conditions in the definition of $C_{J}$ , then $q + t w \in F$ for all sufficiently small $t > 0$ : the affine equations are preserved, coordinates outside $J$ remain nonnegative, and the finitely many positive coordinates of $q$ on $J$ remain positive. By [F2], $⟨ p - q, t w ⟩ \leq 0$ , so $⟨ v, w ⟩ \leq 0$ and $v \in C_{J}$ .

3.1step 2.1step 1.2step 2.2algebra∎

For the nontrivial case of step 2.1, homogeneity and its constant $c$ give $∥ M p - b ∥_{2} = ∥ M (p - q) ∥_{2} = ∥ p - q ∥_{2} ∥ M v ∥_{2} \geq c {dist}_{2} (p, F)$ . Taking $H = 1 / c$ proves the result for $p \notin F$ ; for $p \in F$ the left side is zero. In the empty-unit-section case from step 2.1, $F = Δ_{d}$ and any $H > 0$ works.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Berry–Esseen bound for a finite independent array

Statement

Assume the Axiom of Choice. Let $X_{1}, \dots, X_{n}$ be independent, finite-support real random variables with $E X_{i} = 0$ and total variance $σ^{2} = \sum_{i} E X_{i}^{2} > 0$ . If $S = \sum_{i} X_{i}$ and $Φ$ is the standard-normal CDF, then $\sup_{z \in R} ∣ \Pr {S / σ \leq z} - Φ (z) ∣ \leq 1088 \frac{\sum_{i} E ∣ X_{i} ∣^{3}}{σ^{3}} .$

Facts & Assumptions

Given: The finite independent array, its mean and variance hypotheses, and the Axiom of Choice.

[A1]

The Axiom of Choice and Standard normal and normal laws: assume AC, and let $G$ have density $φ (x) = (2 π)^{- 1 / 2} e^{- x^{2} / 2}$ and total mass one.

[F1]

The exponential function is smooth and $(\exp)^{'} = \exp$ , The exponential dominates every fixed nonnegative integer power at $+ \infty$ , and The Gaussian integral $\int_{- \infty}^{\infty} e^{- x^{2}} d x = \sqrt{π}$ : $φ^{'} (x) = - x φ (x)$ , Gaussian tails vanish at infinity, and the Gaussian integral is finite with the stated normalization.

[F2]

The first fundamental theorem: if $f$ is integrable on $[a, b]$ and continuous at $c$ , then $F^{'} (c) = f (c)$ ; in particular a continuous $f$ has $F$ as a primitive, A continuous function on $[a, b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion, Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , and If $u, v$ are differentiable on $[a, b]$ with $u^{'}, v^{'}$ integrable, then $\int_{a}^{b} u v^{'} = u (b) v (b) - u (a) v (a) - \int_{a}^{b} u^{'} v$ : the first fundamental theorem differentiates a continuous-integrand integral, the product rule applies, and integration by parts holds on finite intervals for integrable derivatives.

[F3]

The second fundamental theorem: if $G$ is differentiable on $[a, b]$ with $G^{'} = f$ and $f$ is integrable, then $\int_{a}^{b} f = G (b) - G (a)$ : on a closed interval, a differentiable function whose derivative is integrable has endpoint difference equal to the derivative's integral; apply it separately on each smooth piece of $f^{'}$ split at the two breakpoints of $h$ .

Proof

1.1givenalgebra

Divide each summand by $σ$ , so it suffices to consider independent mean-zero variables with total variance one and $β : = \sum_{i} E ∣ X_{i} ∣^{3}$ . A zero-variance summand is zero almost surely and may be removed. For $r > 0$ , let $δ_{m} (r)$ be the supremum of ${0}$ together with the normal-CDF errors $\sup_{z} ∣ \Pr {\sum_{i} X_{i} \leq z} - Φ (z)$ over all $m$ -term finite-support arrays with total variance one and third-moment sum at most $r^{3}$ . This convention also defines $δ_{m} (r) = 0$ when the class of arrays is empty.

1.2givenalgebra

If some summand has variance greater than $1 / 2$ , the needed Lyapunov inequality follows locally as follows. Put $A = ∣ X_{i} ∣$ and $m_{3} = E A^{3}$ ; then $m_{3} > 0$ . For $U = A / m_{3}^{1 / 3}$ , the pointwise identity $1 + 2 U^{3} - 3 U^{2} = (U - 1)^{2} (2 U + 1) \geq 0$ gives $E A^{2} / m_{3}^{2 / 3} \leq 1$ , so $E ∣ X_{i} ∣^{3} \geq (E X_{i}^{2})^{3 / 2}$ . Therefore $β \geq (E X_{i}^{2})^{3 / 2} > 1 / (2 \sqrt{2}) > 1 / 3$ . Since any two CDF values differ by at most one, the bound $δ_{m} (r) \leq 1088 r^{3}$ holds in this case.

1.3A1F1F2given

It remains to prove the induction step when each summand variance is at most $1 / 2$ . Fix a threshold $a$ and $ϵ > 0$ , and let $h$ equal $1$ on $(- \infty, a]$ , decrease linearly to $0$ on $[a, a + ϵ]$ , and equal $0$ afterward. Define $f (x) = e^{x^{2} / 2} \int_{- \infty}^{x} e^{- t^{2} / 2} (h (t) - E h (G)) d t,$ where $G$ has the standard-normal law. On any finite interval, [F2] differentiates the integral term and the product rule differentiates the integrating factor, giving $f^{'} (x) - x f (x) = h (x) - E h (G)$ . The total integral of the integrand is zero, so its upper-tail form also holds.

2.1F1F2F3step 1.3

For $x > 0$ , the upper-tail formula and $0 \leq h \leq 1$ give $∣ f (x) ∣ \leq e^{x^{2} / 2} \int_{x}^{\infty} e^{- t^{2} / 2} d t = \int_{0}^{\infty} e^{- x s - s^{2} / 2} d s \leq \min (2, 1 / x)$ . For $x \leq 0$ the lower-tail formula gives the same bounds. Thus $∣ x f (x) ∣ \leq 1$ and the differential equation gives $∣ f^{'} (x) ∣ \leq 2$ . Away from the two breakpoints of the piecewise-linear $h$ , differentiating the Stein equation gives $f^{''} = f + x f^{'} + h^{'}$ , so $∣ f^{''} (x) ∣ \leq 2 + 2 ∣ x ∣ + ϵ^{- 1} 1_{[a, a + ϵ]} (x)$ . On any finite segment, split at those breakpoints and apply [F3] on each smooth subinterval to the function $f^{'}$ ; it is differentiable there, its derivative $f^{''}$ is continuous up to the one-sided endpoints, and hence integrable. Continuity of $f^{'}$ lets the increments add across the breakpoints.

3.1A1F1step 2.1giveninductionalgebra

Integrating the last bound along the segment from $x$ to $x + y$ (and using $∣ f^{'} ∣ \leq 2$ when $∣ y ∣ > 1$ ) yields $∣ f^{'} (x + y) - f^{'} (x) ∣ \leq 4 ∣ y ∣ (1 + ∣ x ∣ + ϵ^{- 1} \int_{0}^{1} 1_{[a, a + ϵ]} (x + s y) d s) .$ For the sum $S_{- i}$ omitting term $i$ , its variance is at least $1 / 2$ . After dividing by its standard deviation $σ_{- i} \geq 1 / \sqrt{2}$ , its third-moment sum is at most $\sqrt{8} r^{3} < 8 r^{3} = (2 r)^{3}$ , so the induction definition bounds its CDF error by $δ_{m - 1} (2 r)$ . Comparing the two endpoints of any interval of length $ϵ$ with a normal interval, whose density is bounded by one, gives $\Pr {S_{- i} + s y \in [a, a + ϵ]} \leq 2 ϵ + 2 δ_{m - 1} (2 r)$ . Finally, $(E ∣ S_{- i} ∣)^{2} \leq E S_{- i}^{2} = Var (S_{- i}) \leq 1$ , because $E (∣ S_{- i} ∣ - E ∣ S_{- i} ∣)^{2} \geq 0$ . Taking expectations in the increment bound therefore gives $E ∣ f^{'} (S_{- i} + y) - f^{'} (S_{- i}) ∣ \leq 16 ∣ y ∣ (1 + δ_{m - 1} (2 r) / ϵ)$ .

3.2A1F1F2step 1.3step 2.1algebra

Integrating by parts on $[- A, A]$ using [F2] gives $\int_{- A}^{A} f^{'} φ = [f φ]_{- A}^{A} + \int_{- A}^{A} x f φ$ . The boundary term tends to zero because $f$ is bounded by step 2.1 and $φ (A) \to 0$ by [F2]; the integrals converge since $f, f^{'}$ are bounded and $∣ x ∣ φ (x)$ is integrable by [F1]. Hence $E f^{'} (G) = E G f (G)$ . The smoothing inequalities $1_{(- \infty, a]} \leq h_{a} \leq 1_{(- \infty, a + ϵ]}$ show that $\Pr {S \leq a} - Φ (a) \leq E h_{a} (S) - E h_{a} (G) + ϵ$ : the normal mass of an interval of length $ϵ$ is at most $ϵ$ . For the reverse difference, apply the same calculation to $h_{a - ϵ}$ and its corresponding Stein solution; the bounds in step 2.1 are uniform in the threshold. For either smoothing function, the Stein equation identifies the expectation difference as $E [f^{'} (S) - S f (S)]$ , proving the displayed uniform estimate.

4.1step 3.1step 3.2givenalgebra

For the needed moment comparison, write the finite law of $A = ∣ X_{i} ∣$ as values $a_{j}$ with weights $p_{j}$ . For every pair $j, k$ , $a_{j}^{2} a_{k} \leq (2 a_{j}^{3} + a_{k}^{3}) / 3$ , since $2 a^{3} + b^{3} - 3 a^{2} b = (a - b)^{2} (2 a + b) \geq 0$ . Averaging with weights $p_{j} p_{k}$ gives $E X_{i}^{2} E ∣ X_{i} ∣ \leq E ∣ X_{i} ∣^{3}$ . Put $Z = S_{- i}$ . Independence and mean zero give $E [X_{i} f (S)] = E [X_{i}^{2} \int_{0}^{1} f^{'} (Z + t X_{i}) d t]$ , while independence also gives $E [X_{i}^{2} f^{'} (Z)] = E X_{i}^{2} E f^{'} (Z)$ . By step 3.1, conditioning on $X_{i}$ bounds $E [X_{i}^{2} \int_{0}^{1} ∣ f^{'} (Z + t X_{i}) - f^{'} (Z) ∣ d t]$ by $8 E ∣ X_{i} ∣^{3} (1 + δ_{m - 1} (2 r) / ϵ)$ , and the same step bounds $E X_{i}^{2} E ∣ f^{'} (Z + X_{i}) - f^{'} (Z) ∣$ by $16 E X_{i}^{2} E ∣ X_{i} ∣ (1 + δ_{m - 1} (2 r) / ϵ)$ . Decomposing at $f^{'} (Z)$ and using the moment comparison shows $∣ E [X_{i} f (S)] - E X_{i}^{2} E f^{'} (S) ∣ \leq 24 E ∣ X_{i} ∣^{3} (1 + δ_{m - 1} (2 r) / ϵ) \leq 32 E ∣ X_{i} ∣^{3} (1 + δ_{m - 1} (2 r) / ϵ)$ . Summing over $i$ and using $\sum_{i} E X_{i}^{2} = 1$ bounds the difference in step 3.2 by $32 r^{3} (1 + δ_{m - 1} (2 r) / ϵ)$ .

5.1step 1.1step 1.2step 3.2step 4.1algebra∎

Choose $ϵ = 512 r^{3}$ . Steps 3.2 and 4.1 give $δ_{m} (r) \leq 544 r^{3} + \frac{1}{16} δ_{m - 1} (2 r)$ . Inductively, $δ_{m - 1} (2 r) \leq 1088 (2 r)^{3}$ , so the right side is at most $(544 + 544) r^{3} = 1088 r^{3}$ . For one summand with variance one, Lyapunov gives $r^{3} \geq β \geq 1$ , and the trivial CDF bound starts the induction. Combining with step 1.2 proves the normalized claim; undoing the variance normalization proves the Statement.

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

One-letter Gallager and expurgated exponent functions

Definition

Let $W$ be a finite DMC from finite nonempty $X$ to $Y$ , with rates and logarithms in nats. For an input law $P$ and $ρ \geq 0$ , define $E_{0} (ρ, P) : = - \ln \sum_{y \in Y} {(\sum_{x \in X} P (x) W (y ∣ x)^{1 / (1 + ρ)})}^{1 + ρ} .$ Separately, for $ρ \geq 1$ , define $B (x, x^{'}) : = \sum_{y} \sqrt{W (y ∣ x) W (y ∣ x^{'})}$ and $E_{0 x} (ρ, P) : = - ρ \ln \sum_{x, x^{'}} P (x) P (x^{'}) B (x, x^{'})^{1 / ρ} .$ For every $a > 0$ , $0^{a} = 0$ ; thus zero channel transitions and zero Bhattacharyya coefficients contribute zero to these sums. These are one-letter functions at a fixed $P$ ; the global maxima and rate-dependent exponent functions are separate definitions.

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

Finite-channel mutual information is concave in the input law

Statement

Let $X, Y$ be finite nonempty sets and let $V (y ∣ x)$ be a row-stochastic channel. For an input probability vector $P$ , write $I_{P} (V)$ for the mutual information under the joint law $P (x) V (y ∣ x)$ . Then $P \mapsto I_{P} (V)$ is concave: for input laws $P_{0}, P_{1}$ and $λ \in [0, 1]$ , $I_{λ P_{0} + (1 - λ) P_{1}} (V) \geq λ I_{P_{0}} (V) + (1 - λ) I_{P_{1}} (V) .$

Facts & Assumptions

Given: Finite nonempty input and output alphabets, a row-stochastic channel $V$ , two input laws $P_{0}, P_{1}$ , and $λ \in [0, 1]$ .

[F1]

Finite mutual information and Finite distributions, entropy, divergence, and stochastic matrices: $I (X; Y) = D (P_{X Y} ∥ P_{X} \otimes P_{Y})$ and $H (q) = - \sum_{y : q_{y} > 0} q_{y} \ln q_{y}$ , with $0 \ln 0 = 0$ .

[F2]

Finite discrete memoryless channels: each row $V (\cdot ∣ x)$ is a probability vector and the output law is $P V$ .

[F3]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : on $(0, 1]$ , $g (t) = - t \ln t$ has derivative $g^{'} (t) = - \ln t - 1$ .

[F4]

[F5]

The logarithm grows more slowly than every positive real power: $t \ln t \to 0$ as $t ↓ 0$ , so $g$ extends continuously by $g (0) = 0$ .

Proof

1.1F1F2algebra

Expanding the finite KL sum in [F1] under $P (x) V (y ∣ x)$ and grouping the finite terms gives $I_{P} (V) = H (P V) - \sum_{x} P (x) H (V (\cdot ∣ x)) .$ Indeed, the logarithm of the joint-to-product ratio is $\ln V (y ∣ x) - \ln (P V) (y)$ on positive joint support; summing the first term gives the negative conditional entropy and summing the second gives the output entropy. Zero-mass coordinates contribute zero by [F1].

1.2F3F4

For $0 < s < t \leq 1$ , [F3] gives $g^{'} (s) = - \ln s - 1 > - \ln t - 1 = g^{'} (t)$ , since $\ln$ is strictly increasing by its positive derivative and the mean value theorem. If $0 < u < v < w \leq 1$ , apply [F4] to $g$ on $[u, v]$ and $[v, w]$ . The resulting derivative points satisfy $ξ_{1} < ξ_{2}$ , so the left secant slope is at least the right secant slope; rearranging is the concavity inequality for $g$ at $v$ . Thus $g$ is concave on $(0, 1]$ .

2.1F1F5step 1.2algebra

For $u, w \in [0, 1]$ with one endpoint zero, replace that endpoint by a positive sequence tending to zero in the inequality of step 1.2 and use continuity from [F5]. Therefore $g$ is concave on $[0, 1]$ . Summing the scalar concavity inequalities over coordinates proves that finite entropy $H (q) = \sum_{y} g (q_{y})$ is concave on each probability simplex.

3.1step 1.1step 2.1givenalgebra∎

Put $P_{λ} = λ P_{0} + (1 - λ) P_{1}$ . The output law satisfies $P_{λ} V = λ (P_{0} V) + (1 - λ) (P_{1} V)$ , so step 2.1 gives $H (P_{λ} V) \geq λ H (P_{0} V) + (1 - λ) H (P_{1} V)$ . The conditional-entropy term in step 1.1 is linear in $P$ . Subtracting that linear term yields $I_{P_{λ}} (V) \geq λ I_{P_{0}} (V) + (1 - λ) I_{P_{1}} (V)$ , as claimed.

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

Finite Pinsker inequality in Euclidean norm

Statement

Let $P = (p_{i})$ and $Q = (q_{i})$ be probability vectors on a finite nonempty set. With natural logarithms and $D (P ∥ Q) = + \infty$ when $P ≪̸ Q$ , one has $D (P ∥ Q) \geq \frac{1}{2} ∥ P - Q ∥_{1}^{2} \geq \frac{1}{2} ∥ P - Q ∥_{2}^{2} .$

Facts & Assumptions

Given: Finite probability vectors $P, Q$ and the finite KL convention in the Statement.

[F1]

Finite log-sum inequality with support and equality cases: grouping coordinates into two classes cannot increase the finite KL divergence; the grouped divergence is at most the original divergence, including the stated support conventions.

[F2]

Finite Kullback–Leibler divergence: $D (P ∥ Q)$ is the sum of $p_{i} \ln (p_{i} / q_{i})$ over positive $p_{i}$ , and equals $+ \infty$ if a positive $p_{i}$ lies over $q_{i} = 0$ .

[F3]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : logarithmic differentiation and the product rule apply on positive coordinates.

[F4]

The logarithm grows more slowly than every positive real power: $t \ln t \to 0$ as $t ↓ 0$ .

Proof

1.1F2givencasesalgebra

If $P ≪̸ Q$ , the first inequality is immediate because its left side is $+ \infty$ . Otherwise let $A = {i : p_{i} > q_{i}}$ and $d = P (A) - Q (A)$ . Since $\sum_{i} (p_{i} - q_{i}) = 0$ , the positive and negative coordinate differences have equal total magnitude, so $∥ P - Q ∥_{1} = 2 d$ . If $A$ is empty, then $P = Q$ and the claim holds.

2.1F1F2step 1.1algebra

For $A$ and its complement, [F1] gives $D (P ∥ Q) \geq p \ln (p / q) + (1 - p) \ln ((1 - p) / (1 - q))$ , where $p = P (A)$ and $q = Q (A)$ , with endpoint terms interpreted by the same support convention.

3.1F3F4step 2.1given

If $q \in {0, 1}$ , finite divergence and $P ≪ Q$ force $p = q$ , so the binary divergence is zero and $d = 0$ . For $0 < q < 1$ , define $g (p) = p \ln (p / q) + (1 - p) \ln ((1 - p) / (1 - q)) - 2 (p - q)^{2}$ . On $0 < p < 1$ , [F3] and the product rule give $g (q) = g^{'} (q) = 0$ and $g^{''} (p) = 1 / [p (1 - p)] - 4 \geq 0$ . Thus $g$ is convex and minimized at $q$ ; continuity of $t \ln t$ at zero from [F4] extends $g (p) \geq 0$ to $p = 0, 1$ .

4.1step 1.1step 2.1step 3.1algebra∎

Therefore $D (P ∥ Q) \geq 2 d^{2} = \frac{1}{2} ∥ P - Q ∥_{1}^{2}$ . Since $∥ v ∥_{2} \leq ∥ v ∥_{1}$ for every finite vector $v$ , the Euclidean bound follows.

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

Gallager and expurgated input-law maxima are attained

Statement

For a finite DMC $W$ , the functions $P \mapsto E_{0} (ρ, P)$ for each $ρ \geq 0$ and $P \mapsto E_{0 x} (ρ, P)$ for each $ρ \geq 1$ , defined in One-letter Gallager and expurgated exponent functions, are finite and continuous on the input probability simplex. Consequently, each attains a finite maximum there. At $ρ = 0$ , $E_{0} (0, P) = 0$ for every $P$ .

Facts & Assumptions

Given: A finite DMC $W$ , its finite nonempty alphabets, a real $ρ$ in one of the stated ranges, and an input law $P$ .

[F1]

One-letter Gallager and expurgated exponent functions: for $ρ \geq 0$ , $E_{0}$ is the negative logarithm of the finite sum of powers $1 / (1 + ρ)$ and $1 + ρ$ ; for $ρ \geq 1$ , $E_{0 x}$ is $- ρ$ times the logarithm of the finite sum of $P (x) P (x^{'}) B (x, x^{'})^{1 / ρ}$ , with $0^{a} = 0$ for $a > 0$ .

[F2]

Finite discrete memoryless channels: each row $W (\cdot ∣ x)$ is a probability vector.

[F3]

Real powers for positive bases, with the zero-base positive-exponent convention, Continuity and derivatives of positive-base real powers, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, and The exponential function is strictly increasing: $t^{a}$ is continuous for $t > 0$ when $a$ is fixed, $0^{a} = 0$ for $a > 0$ , and $\ln$ and $\exp$ are strictly increasing inverses.

[F4]

A composite of continuous functions is continuous, with no side hypothesis of the kind the composition of limits needs and Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function apply to real functions whose domains are subsets of $R$ . Continuity with respect to the vector $P$ is established directly below using the Euclidean norm.

[F5]

Finite probability vectors and For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: the input simplex is nonempty, closed, and bounded in finite-dimensional Euclidean space, hence compact; every continuous real-valued function on it attains its maximum and minimum.

Proof

1.1F1F3algebrachoose

For any fixed $a > 0$ , the convention in [F3] extends $t \mapsto t^{a}$ continuously to $t = 0$ : given $ϵ > 0$ , put $δ = \exp ((\ln ϵ) / a) > 0$ . If $0 < t < δ$ , monotonicity of $\ln$ gives $a \ln t < \ln ϵ$ , so monotonicity of $\exp$ yields $0 < t^{a} < ϵ$ ; at $t = 0$ the value is zero. Thus every positive real power used in [F1] is continuous on $[0, \infty)$ .

1.2F1F2F3F4givenalgebrachoose

For every $x$ , $B (x, x) = \sum_{y} W (y ∣ x) = 1$ by [F2]. Thus the inner sum in $E_{0 x}$ satisfies $\sum_{x, x^{'}} P (x) P (x^{'}) B (x, x^{'})^{1 / ρ} \geq \sum_{x} P (x)^{2} \geq \frac{1}{∣ X ∣} > 0.$ The last inequality follows from $∣ X ∣ \sum_{x} P (x)^{2} - (\sum_{x} P (x))^{2} = \sum_{x < x^{'}} (P (x) - P (x^{'}))^{2} \geq 0$ . Write $d = ∣ X ∣$ , $c_{x x^{'}} = B (x, x^{'})^{1 / ρ}$ , $C = \sum_{x, x^{'}} c_{x x^{'}} > 0$ , and $T (P) = \sum_{x, x^{'}} c_{x x^{'}} P (x) P (x^{'})$ . For input laws $P, Q$ , their coordinates lie in $[0, 1]$ , so $∣ T (P) - T (Q) ∣ \leq \sum_{x, x^{'}} c_{x x^{'}} (∣ P (x) - Q (x) ∣ + ∣ P (x^{'}) - Q (x^{'}) ∣) \leq 2 C ∥ P - Q ∥_{2} .$ Thus $T$ is continuous on the simplex. At each $P$ , scalar continuity of $\ln$ at $T (P) \geq 1 / d$ supplies a tolerance $η > 0$ such that $∣ t - T (P) ∣ < η$ and $t > 0$ imply $ρ ∣ \ln t - \ln T (P) ∣ < ϵ$ . Taking $∥ P - Q ∥_{2} < η / (2 C)$ proves continuity of $E_{0 x} (ρ, P) = - ρ \ln T (P)$ directly, without applying [F4] on a vector domain.

2.1F1F2F3step 1.1step 1.2algebrachoose

Fix $ρ > 0$ and set $A_{y} (P) = \sum_{x} P (x) W (y ∣ x)^{1 / (1 + ρ)}$ and $S (P) = \sum_{y} A_{y} (P)^{1 + ρ}$ . Since the fixed coefficients in $A_{y}$ lie in $[0, 1]$ , $∣ A_{y} (P) - A_{y} (Q) ∣ \leq d ∥ P - Q ∥_{2}$ . At a fixed $P$ and for $ϵ > 0$ , step 1.1 supplies, for each of the finitely many $y$ , a scalar tolerance $η_{y} > 0$ such that $∣ t - A_{y} (P) ∣ < η_{y}$ with $t \geq 0$ implies $∣ t^{1 + ρ} - A_{y} (P)^{1 + ρ} ∣ < ϵ / ∣ Y ∣$ . Taking $∥ P - Q ∥_{2} < \min_{y} η_{y} / d$ and summing proves $∣ S (P) - S (Q) ∣ < ϵ$ . For every input law $P$ , some $x$ has $P (x) > 0$ ; since row $W (\cdot ∣ x)$ sums to one, some $y$ has $W (y ∣ x) > 0$ , giving $A_{y} (P) > 0$ and hence $S (P) > 0$ . Scalar logarithm continuity at $S (P)$ , followed by the just-proved continuity estimate for $S$ , therefore gives continuity of the real-valued $E_{0} (ρ, P) = - \ln S (P)$ . At $ρ = 0$ , the sum is $\sum_{y} \sum_{x} P (x) W (y ∣ x) = 1$ , so $E_{0} (0, P) = 0$ .

3.1F5step 1.2step 2.1∎

The finite probability vectors form the nonempty simplex $Δ = {P : P (x) \geq 0, \sum_{x} P (x) = 1}$ by [F5]. It is nonempty because a point mass belongs to it; each coordinate lies in $[0, 1]$ , so it is bounded; and the coordinate inequalities are closed half-spaces while the sum equation is a closed affine hyperplane, so $Δ$ is closed. Heine–Borel makes $Δ$ compact, and steps 1.2 and 2.1 show that each objective is continuous and real-valued on it. The extreme-value assertion in [F5] therefore gives an attained finite maximum for every stated $ρ$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Conditional information variance and DMC dispersion

Definition

Let $P$ be an input probability vector for the finite DMC $W$ , and let $P_{Y} (y) = \sum_{x} P (x) W (y ∣ x)$ . On cells with $P (x) W (y ∣ x) > 0$ , define $ı_{P} (x; y) = \ln [W (y ∣ x) / P_{Y} (y)]$ ; the denominator is then positive. Put $V (P, W) : = \sum_{x : P (x) > 0} P (x) {Var}_{W (\cdot ∣ x)} [ı_{P} (x; Y)] .$ Let $C (W) = \max_{P} I (P, W)$ and $Π (W) = {P : I (P, W) = C (W)}$ , the nonempty set of capacity-achieving input distributions. Define $V_{\min} (W) : = \min_{P \in Π (W)} V (P, W), V_{\max} (W) : = \max_{P \in Π (W)} V (P, W) .$ The local attainment lemma DMC minimum and maximum dispersion are attained ↗ proves these extrema exist. Dispersion is measured in nats squared. In the normal-approximation theorem on this page only the fixed range $0 < ϵ < 1 / 2$ and premise $V_{\min} (W) > 0$ are used.

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

Gallager, random-coding, expurgated, and sphere-packing functions

Definition

Let $W$ be a finite unconstrained DMC from finite nonempty $X$ to $Y$ , with rates and logarithms in nats. The one-letter function $E_{0} (ρ, P)$ for $ρ \geq 0$ and $E_{0 x} (ρ, P)$ for $ρ \geq 1$ are defined in One-letter Gallager and expurgated exponent functions. Their maxima over the input simplex are attained and finite by Gallager and expurgated input-law maxima are attained. For every $ρ \geq 0$ , define $E_{0} (ρ) : = \max_{P} E_{0} (ρ, P)$ ; on the random-coding range set $E_{r} (R) : = \sup_{0 \leq ρ \leq 1} {E_{0} (ρ) - ρ R} .$ The expurgated function and sphere-packing expression are $E_{e x} (R) : = \sup_{ρ \geq 1} {\max_{P} E_{0 x} (ρ, P) - ρ R}, E_{s p} (R) : = \sup_{ρ \geq 0} {E_{0} (ρ) - ρ R} .$ These functions define lower or upper bounds used on this page; they do not assert that an error-exponent limit exists or that the sphere-packing bound applies without its later strict-feasibility hypothesis.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Average and maximal error reliability exponents

Definition

For a finite DMC $W$ , $R > 0$ , and $n \geq 1$ , set $M_{n} = ⌈ e^{n R} ⌉$ . Let $P_{k}^{*} (n, M_{n})$ be the minimum error probability among length- $n$ deterministic codes of that size under criterion $k \in {a v, m a x}$ , where the two errors are those of Average and maximal error of a fixed-length code. This minimum exists because the encoder and decoder range over finite sets. Define $E_{k}^{-} (R) : = {lim inf}_{n \to \infty} - \frac{1}{n} \ln P_{k}^{*} (n, M_{n}), E_{k}^{+} (R) : = {lim sup}_{n \to \infty} - \frac{1}{n} \ln P_{k}^{*} (n, M_{n}),$ with $- \ln 0 = + \infty$ . An error-exponent limit $E_{k} (R)$ is used only when the liminf and limsup agree in the extended reals. These are exponents of error probability; the exponent of success probability is a different quantity. No general exact formula for the finite-DMC reliability function is part of this definition.

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

The capacity-achieving output law is unique

Statement

For a finite DMC $W$ , every input law attaining $C (W) = \max_{P} I (P, W)$ induces the same output law $Q^{*}$ . This output law is unique even when the capacity-achieving input law is not.

Facts & Assumptions

Given: A finite DMC $W$ and $C (W) = \max_{P} I (P, W)$ .

[F1]

Finite DMC information capacity is attained: at least one input law attains $C (W)$ .

[F2]

Single-letter information capacity of a finite DMC: $C (W)$ is the maximum of $I (P, W)$ over input probability vectors.

[F3]

Finite mutual information and Finite distributions, entropy, divergence, and stochastic matrices: finite mutual information is the finite joint/product KL sum and $H (q) = - \sum_{y : q_{y} > 0} q_{y} \ln q_{y}$ .

[F4]

Finite discrete memoryless channels: every row $W (\cdot ∣ x)$ is a probability vector and $P W$ is the induced output law.

[F5]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : logarithmic differentiation and the product rule apply on positive coordinates.

[F6]

The logarithm grows more slowly than every positive real power: $t \ln t \to 0$ as $t ↓ 0$ .

Proof

1.1F3F4givenalgebra

Expanding the finite KL sum in [F3] for the joint law $P (x) W (y ∣ x)$ and grouping its finite terms gives $I (P, W) = H (P W) - \sum_{x} P (x) H (W (\cdot ∣ x)) .$ Terms with zero probability are omitted, so this identity also holds on the boundary of the input simplex.

1.2F3F4F5F6given

Suppose capacity-achieving laws $P_{0}, P_{1}$ have distinct outputs $Q_{0}, Q_{1}$ . Their midpoint input $\overset{ˉ}{P} = (P_{0} + P_{1}) / 2$ has output $\overset{ˉ}{Q} = (Q_{0} + Q_{1}) / 2$ . The scalar function $- t \ln t$ is strictly concave for $t > 0$ because its second derivative, computed using [F3] and the product rule, is $- 1 / t$ ; continuity at $0$ from [F6] and the direct identity $- \frac{t}{2} \ln \frac{t}{2} > - \frac{t}{2} \ln t$ when one endpoint is zero extend strict concavity to the closed interval. Hence finite entropy is strictly concave and $H (\overset{ˉ}{Q}) > (H (Q_{0}) + H (Q_{1})) / 2$ .

2.1F1F2step 1.1step 1.2assume-contradischarge-contradiction∎

The second term in step 1.1 is linear in $P$ , so step 1.2 gives $I (\overset{ˉ}{P}, W) > (I (P_{0}, W) + I (P_{1}, W)) / 2 = C (W)$ , contradicting [F2]. Existence in [F1] and this contradiction show that all capacity-achieving input laws induce one common output law.

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

Globally optimized constant-composition and Gallager functions agree

Statement

Let $W$ be a finite DMC. For each $ρ > 0$ and input law $P$ , define $E_{0, c c} (ρ, P) : = \inf_{V : V (\cdot ∣ x) ≪ W (\cdot ∣ x)} {\sum_{x} P (x) D (V (\cdot ∣ x) ∥ W (\cdot ∣ x)) + ρ I_{P} (V)},$ where $V$ ranges over row-stochastic channels on the same alphabets, $I_{P} (V)$ is the mutual information of $P (x) V (y ∣ x)$ , and terms with $P (x) = 0$ are omitted. At $ρ = 0$ , set $E_{0, c c} (0, P) = 0$ . Then $\max_{P} E_{0, c c} (ρ, P) = \max_{P} E_{0} (ρ, P),$ with $E_{0}$ from Gallager, random-coding, expurgated, and sphere-packing functions. This equality holds for every $ρ > 0$ and is after optimizing over $P$ ; it is not asserted for each fixed $P$ . At $ρ = 0$ , both sides are zero under the stated conventions.

Facts & Assumptions

Given: A finite DMC $W$ , a parameter $ρ > 0$ , and the finite KL and mutual-information conventions.

[F1]

One-letter Gallager and expurgated exponent functions: $E_{0} (ρ, P) = - \ln \sum_{y} (\sum_{x} P (x) W (y ∣ x)^{1 / (1 + ρ)})^{1 + ρ}$ .

[F2]

Finite mutual information: $I_{P} (V)$ is $D (P V_{X Y} ∥ P \otimes P V_{Y})$ .

[F3]

Finite Kullback–Leibler divergence and Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL is support-aware, nonnegative, and vanishes exactly at equal probability vectors.

[F4]

For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: every nonempty closed bounded subset of finite-dimensional Euclidean space is compact, and each continuous real-valued function on it attains its minimum and maximum.

[F5]

Real powers for positive bases, with the zero-base positive-exponent convention and Continuity and derivatives of positive-base real powers: for $t > 0$ , $t^{a} = \exp (a \ln t)$ and $(t^{a})^{'} = a t^{a - 1}$ ; for $a > 0$ , the zero-base convention is $0^{a} = 0$ .

[F6]

The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : the scalar chain and product rules apply to the differentiable power and logarithm formulas on positive arguments.

[F7]

Absolute real powers are Borel measurable and convex: for every $p \geq 1$ , $t \mapsto ∣ t ∣^{p}$ is continuous and convex on $R$ .

[F8]

A twice-differentiable function on an open interval is convex if and only if its second derivative is nonnegative: a twice-differentiable function on an open interval is convex when its second derivative is nonnegative.

[F9]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm and The exponential function is strictly increasing: $\ln$ and $\exp$ are strictly increasing inverses on their positive domains.

[F10]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\ln^{'} (z) = 1 / z$ for $z > 0$ .

Proof

1.1F1F3givenalgebracases

Put $α = (1 + ρ)^{- 1} \in (0, 1)$ and, for an output law $Q$ , set $Z_{x} (Q) = \sum_{y} W (y ∣ x)^{α} Q (y)^{1 - α}$ . If $Z_{x} (Q) > 0$ , define $R_{x} (y) = W (y ∣ x)^{α} Q (y)^{1 - α} / Z_{x} (Q)$ . Expanding the finite sums gives for every $V_{x} ≪ W_{x}$ with finite $D (V_{x} ∥ Q)$ $D (V_{x} ∥ W_{x}) + ρ D (V_{x} ∥ Q) = (1 + ρ) D (V_{x} ∥ R_{x}) - (1 + ρ) \ln Z_{x} (Q) .$ By [F3], the minimum over $V_{x}$ is $- (1 + ρ) \ln Z_{x} (Q) = - α^{- 1} \ln Z_{x} (Q)$ . If $Z_{x} (Q) = 0$ , every such objective with positive $P (x)$ is infinite, matching the extended value of this expression.

1.2F1F4F7F9givenalgebra

Define $S_{y} (P) = \sum_{x} P (x) W (y ∣ x)^{α}$ and $Ψ (P) = \sum_{y} S_{y} (P)^{1 / α}$ . Then [F1] gives $E_{0} (ρ, P) = - \ln Ψ (P)$ . Since $1 / α = 1 + ρ > 1$ , [F7] shows that each summand $S_{y} (P)^{1 / α}$ is continuous and convex as a function of $P$ ; hence $Ψ$ is continuous and convex on the input simplex. The simplex is nonempty because it contains a point mass, closed as the intersection of finitely many coordinate half-spaces with the affine equation $\sum_{x} P (x) = 1$ , and bounded because every coordinate lies in $[0, 1]$ . By [F4] it is compact, so $Ψ$ attains a minimum at some $P^{*}$ . For every input law at least one coordinate of $P$ is positive, and that row of $W$ has a positive entry; hence at least one $S_{y} (P) > 0$ and $Ψ (P) > 0$ . Also, for every $r > 0$ , $t^{r} \to 0$ as $t ↓ 0$ : given $ε > 0$ , take $δ = ε^{1 / r}$ ; if $0 < t < δ$ , strict monotonicity of $\ln$ and $\exp$ gives $t^{r} < ε$ . Write $S_{y} = S_{y} (P^{*})$ , $Ψ_{*} = Ψ (P^{*}) > 0$ , $T = {y : S_{y} > 0}$ , and $q^{*} (y) = S_{y}^{1 / α} / Ψ_{*}$ on $T$ , with $q^{*} (y) = 0$ outside $T$ .

2.1F2F3step 1.1algebra

For any $V$ and output law $Q$ , expansion of finite KL gives $\sum_{x} P (x) D (V_{x} ∥ Q) = I_{P} (V) + D (P V_{Y} ∥ Q) \geq I_{P} (V),$ with equality at $Q = P V_{Y}$ by [F2–F3]. Taking the joint infimum over $V, Q$ and applying step 1.1 row by row therefore yields $E_{0, c c} (ρ, P) = \inf_{Q} \sum_{x : P (x) > 0} P (x) f_{x} (Q), f_{x} (Q) : = - α^{- 1} \ln Z_{x} (Q),$ with $f_{x} (Q) = + \infty$ when $Z_{x} (Q) = 0.$ Coordinates with $P (x) = 0$ are omitted, so no $0 \cdot \infty$ term is used.

2.2F1F5F6step 1.2algebra

Put $T_{x} = \sum_{y} W (y ∣ x)^{α} S_{y}^{ρ}$ . For each $x$ , move from $P^{*}$ toward the point mass $δ_{x}$ along $P_{t} = (1 - t) P^{*} + t δ_{x}$ , so $S_{y} (P_{t}) = S_{y} + t (W (y ∣ x)^{α} - S_{y})$ . If $S_{y} > 0$ , [F5]–[F6] give the derivative of $S_{y} (P_{t})^{1 / α}$ at $t = 0$ as $α^{- 1} S_{y}^{ρ} (W (y ∣ x)^{α} - S_{y})$ . If $S_{y} = 0$ , the term equals $t^{1 / α} W (y ∣ x)$ , whose right derivative at zero is zero because $1 / α - 1 = ρ > 0$ and the endpoint limit in step 1.2 applies. Therefore the right derivative of $Ψ (P_{t})$ at zero is $α^{- 1} (T_{x} - Ψ_{*})$ , using $\sum_{y} S_{y}^{1 / α} = Ψ_{*}$ . The minimum at $t = 0$ makes this right derivative nonnegative, so $T_{x} \geq Ψ_{*}$ . Also $\sum_{x} P^{*} (x) T_{x} = \sum_{y} S_{y}^{1 + ρ} = Ψ_{*}$ . Since every $T_{x} \geq Ψ_{*}$ and this weighted average equals $Ψ_{*}$ , equality holds whenever $P^{*} (x) > 0$ . Substitution into $Z_{x} (q^{*}) = Ψ_{*}^{- (1 - α)} T_{x}$ gives $Z_{x} (q^{*}) \geq Ψ_{*}^{α}$ , with equality for every active input. Thus $f_{x} (q^{*}) \leq - \ln Ψ_{*}$ for all $x$ , with equality on $supp P^{*}$ .

3.1step 2.1step 2.2algebra

Applying step 2.1 with the particular output law $q^{*}$ gives, for every $P$ , $E_{0, c c} (ρ, P) \leq \sum_{x} P (x) f_{x} (q^{*}) \leq - \ln Ψ_{*} = \max_{P^{'}} E_{0} (ρ, P^{'}) .$ Therefore $\max_{P} E_{0, c c} (ρ, P) \leq \max_{P} E_{0} (ρ, P)$ .

3.2F5F6F8F9F10step 1.2step 2.2

On $[0, \infty)$ , the power $t^{1 - α}$ is continuous by the endpoint estimate in step 1.2 and concave: on $(0, \infty)$ the second derivative of $- t^{1 - α}$ is $(1 - α) α t^{- 1 - α} > 0$ , so [F5], [F6], and [F8] make $- t^{1 - α}$ convex there; continuity extends the concavity inequality to zero. Thus each $Z_{x} (Q)$ is concave. The function $- \ln z$ is decreasing and convex on $(0, \infty)$ , since $\ln$ is increasing by [F9] and $(- \ln z)^{''} = z^{- 2} > 0$ by [F5], [F6], [F8], and [F10]. Consequently $f_{x} (Q) = - α^{- 1} \ln Z_{x} (Q)$ is convex wherever $Z_{x} (Q) > 0$ : concavity of $Z_{x}$ , monotonicity of $- \ln$ , and convexity of $- \ln$ give the convex-combination inequality directly. Hence $F (Q) = \sum_{x : P^{*} (x) > 0} P^{*} (x) f_{x} (Q)$ is convex on its finite domain. For $y \in T$ , differentiating at the positive point $q^{*}$ and using $Z_{x} (q^{*}) = Ψ_{*}^{α}$ for active $x$ from step 2.2 gives $\frac{\partial F}{\partial Q (y)} (q^{*}) = - \frac{1 - α}{α} \frac{Ψ_{*}^{α}}{S_{y}} \frac{\sum_{x : P^{*} (x) > 0} P^{*} (x) W (y ∣ x)^{α}}{Ψ_{*}^{α}} = - ρ .$ For any strictly positive probability vector $Q$ on $T$ , let $g (t) = F ((1 - t) q^{*} + t Q)$ . It is convex, and $g_{+}^{'} (0) = \sum_{y \in T} (- ρ) (Q (y) - q^{*} (y)) = 0$ . Convexity gives $(g (t) - g (0)) / t \leq g (1) - g (0)$ for $0 < t < 1$ ; letting $t ↓ 0$ yields $F (Q) \geq F (q^{*})$ . If $Q$ has zero coordinates on $T$ but $F (Q) < \infty$ , then every active $Z_{x} (Q) > 0$ ; apply the result to $Q_{t} = (1 - t) Q + t q^{*}$ and let $t ↓ 0$ , using continuity of the finite sums and logarithms on positive $Z_{x} (Q)$ . If $F (Q) = + \infty$ , the inequality is immediate. Thus $F (Q) \geq F (q^{*})$ for every probability vector supported on $T$ .

4.1step 2.2step 3.2casesalgebra

For a general output law $Q$ , let $c = Q (T)$ . If $c = 0$ , every active row has $Z_{x} (Q) = 0$ and $F (Q) = + \infty$ . If $c > 0$ , normalize $Q_{T} = Q (\cdot ∣ T)$ . Every active row is supported on $T$ , so $Z_{x} (Q) = c^{1 - α} Z_{x} (Q_{T})$ and $f_{x} (Q) = f_{x} (Q_{T}) - ρ \ln c \geq f_{x} (Q_{T})$ . Step 3.2 then gives $F (Q) \geq F (q^{*})$ . Since active inputs satisfy $f_{x} (q^{*}) = - \ln Ψ_{*}$ , step 2.1 yields $E_{0, c c} (ρ, P^{*}) = F (q^{*}) = - \ln Ψ_{*} = \max_{P} E_{0} (ρ, P)$ .

5.1step 3.1step 4.1algebra∎

Step 4.1 gives $\max_{P} E_{0, c c} (ρ, P) \geq E_{0, c c} (ρ, P^{*}) = \max_{P} E_{0} (ρ, P)$ , while step 3.1 gives the reverse inequality. This proves the globally optimized identity and establishes no pointwise-in- $P$ equality.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Finite-DMC dependence-testing achievability bound

Statement

Let $W^{n}$ be the block channel of a finite DMC, let $P_{X^{n}}$ be any input law, and let $M \geq 2$ . Define the charged information density $ı (x^{n}; y^{n}) = \ln [W^{n} (y^{n} ∣ x^{n}) / (P_{X^{n}} W^{n}) (y^{n})]$ on the support of $P_{X^{n}} W^{n}$ . There is a deterministic length- $n$ code with $M$ messages and average error at most $E \exp (- {[ı (X^{n}; Y^{n}) - \ln \frac{M - 1}{2}]}_{+}),$ where $(X^{n}, Y^{n}) \sim P_{X^{n}} W^{n}$ . For $M = 1$ , a zero-error code exists. The conclusion is an average-error bound and does not by itself bound every message's error.

Facts & Assumptions

Given: A finite DMC, its product block kernel $W^{n}$ , an input law $P_{X^{n}}$ , and an integer $M \geq 2$ .

[F1]

Finite discrete memoryless channels and The DMC product laws are stochastic kernels: the block law is $W^{n} (y^{n} ∣ x^{n}) = \prod_{i} W (y_{i} ∣ x_{i})$ and is a stochastic kernel.

[F2]

Finite DMC information density: information density is the natural-log likelihood ratio between the channel output law given the input and the output marginal, evaluated on charged support.

[F3]

Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: a code has a deterministic encoder and decoder, and its average error is the uniform-message average of its message errors.

Proof

1.1F1F2F3givenconstruct

Draw codewords $X^{n} (1), \dots, X^{n} (M)$ independently from $P_{X^{n}}$ . Put $Q = P_{X^{n}} W^{n}$ and $τ = \ln ((M - 1) / 2)$ . For decoder tests extend $ı (x^{n}; y^{n})$ to $- \infty$ whenever $P_{X^{n}} (x^{n}) W^{n} (y^{n} ∣ x^{n}) = 0$ ; on its positive support $Q (y^{n}) > 0$ , so the stated logarithm is finite. The decoder selects the lowest index $j$ for which $ı (X^{n} (j); y^{n}) > τ$ ; if no index passes, it outputs message $1$ . This defines a deterministic code decoder for each realized codebook.

2.1F1F2step 1.1

If message $j$ is sent, an error can occur only if its own test fails or an earlier codeword passes. Thus its conditional error is at most $\Pr [ı (X^{n} (j); Y^{n}) \leq τ ∣ X^{n} (j)] + \sum_{k < j} \Pr [ı (X^{n} (k); Y^{n}) > τ ∣ X^{n} (j)] .$ The first probability averaged over the true codeword and output is $\Pr_{P_{X^{n}} W^{n}} [ı \leq τ]$ . Each earlier independent codeword and the true output have law $P_{X^{n}} \otimes Q$ , so its averaged term is $\Pr_{P_{X^{n}} \otimes Q} [ı > τ]$ .

3.1F2step 2.1algebra

Averaging over the uniform message index gives ensemble-average error at most $\Pr_{P_{X^{n}} W^{n}} [ı \leq τ] + \frac{M - 1}{2} \Pr_{P_{X^{n}} \otimes Q} [ı > τ],$ because $M^{- 1} \sum_{j = 1}^{M} (j - 1) = (M - 1) / 2$ . On the event $ı > τ$ , the likelihood ratio identity gives $\Pr_{P \otimes Q} [ı > τ] = E_{P W} [e^{- ı} 1_{{ı > τ}}]$ . Therefore this bound equals $E_{P W} [e^{- (ı - τ)_{+}}]$ .

4.1F3step 3.1choose∎

The finite random codebook ensemble has some realization whose average error is no larger than its expectation; otherwise every realization would exceed the ensemble average. With $τ = \ln ((M - 1) / 2)$ , this realization proves the stated bound. A one-message code has no decoding error.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Finite-DMC hypothesis-testing meta-converse

Statement

Let a finite-DMC code have $M \geq 1$ messages and average error $ϵ$ . For any output probability vector $Q_{Y^{n}}$ , let $P_{M Y^{n}} (m, y^{n}) = M^{- 1} W^{n} (y^{n} ∣ x_{m}^{n})$ be the true joint law and let ${\tilde{Q}}_{M Y^{n}} (m, y^{n}) = M^{- 1} Q_{Y^{n}} (y^{n})$ . With the type-II testing function $β_{ϵ}$ of Finite type-II testing function with explicit orientation, which constrains rejection under its first argument, one has $β_{ϵ} (P_{M Y^{n}}, {\tilde{Q}}_{M Y^{n}}) \leq \frac{1}{M} .$

Facts & Assumptions

Given: A deterministic length- $n$ code with $M$ messages, average error $ϵ$ , and any output probability vector $Q_{Y^{n}}$ .

[F1]

Finite type-II testing function with explicit orientation: $β_{ϵ} (P, Q)$ is the infimum of $E_{Q} (1 - ϕ)$ over tests $0 \leq ϕ \leq 1$ with $E_{P} ϕ \leq ϵ$ ; the first law is the null and the second is the alternative.

[F2]

Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: the decoder is a deterministic map $d : Y^{n} \to [M]$ , and the average error is the uniform-message error probability.

[F3]

Finite discrete memoryless channels and The DMC product laws are stochastic kernels: $W^{n} (\cdot ∣ x_{m}^{n})$ is a probability vector for every codeword.

Proof

1.1F1F2F3givenalgebra

Define $ϕ (m, y^{n}) = 1 {d (y^{n}) \neq m}$ . Under the true law $P_{M Y^{n}}$ , $E_{P} ϕ = ϵ$ , so $ϕ$ is feasible in [F1]. Under $\tilde{Q}$ , its type-II error is $E_{\tilde{Q}} (1 - ϕ) = \frac{1}{M} \sum_{m = 1}^{M} \sum_{y^{n}} Q_{Y^{n}} (y^{n}) 1 {d (y^{n}) = m} = \frac{1}{M},$ since for each output exactly one message is decoded. No likelihood ratio is used, so zeros in $Q_{Y^{n}}$ cause no support problem.

2.1F1step 1.1algebra∎

The infimum over all feasible tests in [F1] is at most the value of the particular test in step 1.1. This gives the claimed bound for every auxiliary output law, including singular ones.

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

A CAID's information-density variance equals its conditional dispersion

Statement

For every CAID $P \in Π (W)$ , let $Q^{*} = P W$ and let $(X, Y) \sim P (x) W (y ∣ x)$ . For every $x$ with $P (x) > 0$ , $E [\ln (W (Y ∣ x) / Q^{*} (Y)) ∣ X = x] = C (W),$ and $Var [\ln (W (Y ∣ X) / Q^{*} (Y))] = V (P, W) .$

Facts & Assumptions

Given: A finite DMC and a capacity-achieving input law $P$ .

[F1]

Finite DMC information capacity is attained: $P$ is a maximizer of $I (P, W)$ and $I (P, W) = C (W)$ .

[F2]

The capacity-achieving output law is unique: every CAID induces the same output law $Q^{*}$ .

[F3]

Capacity-achieving output laws bound every row divergence: each row is supported on $Q^{*}$ and has divergence $d_{x} : = D (W (\cdot ∣ x) ∥ Q^{*}) \leq C (W)$ .

[F4]

Finite mutual information: $I (P, W)$ is the KL divergence of the joint law $P (x) W (y ∣ x)$ from its product marginals.

[F5]

Conditional information variance and DMC dispersion: $V (P, W) = \sum_{x} P (x) {Var}_{W_{x}} \ln [W (Y ∣ x) / (P W) (Y)]$ .

Proof

1.1F1F2F3F4givenalgebra

Since $Q^{*} = P W$ , [F4] expands to $I (P, W) = \sum_{x} P (x) D (W (\cdot ∣ x) ∥ Q^{*}) = \sum_{x} P (x) d_{x}$ . By [F1], this average is $C (W)$ , while [F3] gives $d_{x} \leq C (W)$ for every $x$ . Therefore each $x$ with $P (x) > 0$ has $d_{x} = C (W)$ ; otherwise the weighted average would be strictly smaller.

2.1F3F5step 1.1givenalgebra∎

Under the joint law, the conditional mean of $Z = \ln [W (Y ∣ X) / Q^{*} (Y)]$ given $X = x$ is $d_{x}$ . Step 1.1 makes this mean the constant $C (W)$ on every positive-mass input. Hence $E Z = C (W)$ and $Var (Z) = E [(Z - C (W))^{2}] = \sum_{x} P (x) {Var}_{W_{x}} (Z) = V (P, W),$ where the last equality is [F5]. All terms are finite because the alphabets and charged supports are finite.

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

DMC minimum and maximum dispersion are attained

Statement

For every finite DMC, the set $Π (W)$ of capacity-achieving input laws is nonempty and compact, and the function $P \mapsto V (P, W)$ is continuous on $Π (W)$ . Therefore $V_{\min} (W)$ and $V_{\max} (W)$ in Conditional information variance and DMC dispersion are attained.

Facts & Assumptions

Given: A finite DMC and the definitions of $C (W)$ , $Π (W)$ , and $V (P, W)$ .

[F1]

Finite DMC information capacity is attained: a capacity-achieving input law exists.

[F2]

The capacity-achieving output law is unique: all capacity-achieving inputs induce the same output law $Q^{*}$ .

[F3]

Capacity-achieving output laws bound every row divergence: every row is supported on $Q^{*}$ , and $D (W (\cdot ∣ x) ∥ Q^{*}) \leq C (W)$ .

[F4]

Conditional information variance and DMC dispersion: $V (P, W)$ is the $P$ -average of row conditional variances of $\ln [W (Y ∣ x) / (P W) (Y)]$ .

[F5]

For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: the finite-dimensional probability simplex is compact, and a continuous function on a nonempty compact set attains its extrema.

[F6]

Finite mutual information and Finite distributions, entropy, divergence, and stochastic matrices: finite mutual information has the finite entropy expansion, with $0 \ln 0 = 0$ .

[F7]

The logarithm grows more slowly than every positive real power: $t \ln t \to 0$ as $t ↓ 0$ .

[F8]

Single-letter information capacity of a finite DMC: $C (W) = \max_{P} I (P, W)$ and $Π (W)$ is its maximizing level set.

Proof

1.1F5F6F7F8given

The input simplex is compact by [F5]. Expanding the KL sum in [F6] gives $I (P, W) = H (P W) - \sum_{x} P (x) H (W_{x})$ . This finite entropy formula is continuous: [F7] gives $t \ln t \to 0$ at zero. By [F8], $Π (W) = {P : I (P, W) = C (W)}$ is the maximizing level set and is closed in the simplex.

1.2F2F3given

For $P \in Π (W)$ , [F2] gives $P W = Q^{*}$ , and [F3] says each row is supported on $Q^{*}$ . On every reachable output $y$ , $Q^{*} (y) > 0$ : some row has $W (y ∣ x) > 0$ , and [F3] requires that row's support to lie in $Q^{*}$ . Consequently each row variance $v_{x} : = {Var}_{W (\cdot ∣ x)} \ln [W (Y ∣ x) / Q^{*} (Y)]$ is a finite constant independent of $P \in Π (W)$ .

2.1F1step 1.1

By [F1], $Π (W)$ is nonempty; step 1.1 makes it a closed subset of a compact set, hence compact.

3.1F4F5step 2.1step 1.2algebra∎

On $Π (W)$ , [F4] therefore becomes $V (P, W) = \sum_{x} P (x) v_{x}$ , a finite linear function of $P$ , hence continuous. Applying [F5] to the compact nonempty set from step 2.1 proves attainment of its minimum and maximum.

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

Finite-DMC information deficit controls squared distance to the CAID set

Statement

Let $W$ be a finite DMC, $C = C (W)$ , and $Π = {P : I (P, W) = C}$ . There is $α > 0$ , depending on $W$ , such that every input law $P$ satisfies $C - I (P, W) \geq α {dist}_{2} (P, Π)^{2} .$

Facts & Assumptions

Given: A finite DMC $W$ , its capacity $C$ , and its nonempty CAID set $Π$ .

[F1]

The capacity-achieving output law is unique: every $P^{*} \in Π$ induces one common output law $Q^{*}$ .

[F2]

Capacity-achieving output laws bound every row divergence: every row $W_{x}$ is supported on $Q^{*}$ and $d_{x} : = D (W_{x} ∥ Q^{*}) \leq C$ .

[F3]

Finite mutual information and Finite Kullback–Leibler divergence: finite mutual information and KL are the support-aware finite sums in the direction $D (P ∥ Q)$ .

[F4]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL is nonnegative and equals zero exactly when its probability vectors agree.

[F5]

Finite Pinsker inequality in Euclidean norm: $D (R ∥ Q) \geq \frac{1}{2} ∥ R - Q ∥_{2}^{2}$ for finite probability vectors.

[F6]

Error bound for a finite simplex and affine slice: for a nonempty affine slice $F$ of a finite simplex, ${dist}_{2} (P, F) \leq H ∥ M P - b ∥_{2}$ for its defining linear map and target.

Proof

1.1F2F3givenalgebra

Fix a CAID and let $Q^{*}$ be its output. For every input law $P$ , expanding the finite sums using [F2]–[F3] gives $C - I (P, W) = \sum_{x} P (x) (C - d_{x}) + D (P W ∥ Q^{*}) .$ Indeed, $\sum_{x} P (x) d_{x} - I (P, W) = \sum_{y} (P W) (y) \ln [(P W) (y) / Q^{*} (y)]$ .

2.1F1F2F4step 1.1algebra

Put $E = {x : d_{x} = C}$ . By [F2] and [F4], the right side of step 1.1 vanishes exactly when $P (x) = 0$ for $x \notin E$ and $P W = Q^{*}$ . Thus $Π = {P \in Δ_{X} : P ∣_{E^{c}} = 0, P W = Q^{*}}$ , a nonempty affine slice of the input simplex.

2.2F2F5step 1.1givenalgebra

If $E^{c} \neq \emptyset$ , let $η = \min_{x \notin E} (C - d_{x}) > 0$ . The first term in step 1.1 is at least $η ∥ P ∣_{E^{c}} ∥_{2}^{2}$ , since $P (x) \in [0, 1]$ and $\sum_{E^{c}} P (x) \geq ∥ P ∣_{E^{c}} ∥_{2} \geq ∥ P ∣_{E^{c}} ∥_{2}^{2}$ . By [F5], the second term is at least $\frac{1}{2} ∥ P W - Q^{*} ∥_{2}^{2}$ . Hence the gap is at least $a$ times the squared norm of the concatenated residual $(P ∣_{E^{c}}, P W - Q^{*})$ , with $a = \min (η, 1 / 2)$ . If $E^{c} = \emptyset$ , omit that block and take $a = 1 / 2$ .

3.1F6step 2.1step 2.2casesalgebra∎

Apply [F6] to the slice in step 2.1 with linear map $P \mapsto (P ∣_{E^{c}}, P W)$ and target $(0, Q^{*})$ , omitting the first component when $E^{c} = \emptyset$ . For its finite constant $H$ , step 2.2 gives $C - I (P, W) \geq a H^{- 2} {dist}_{2} (P, Π)^{2}$ . If $Π$ is the whole simplex, the distance is identically zero and any positive $α$ works; otherwise take $α = a H^{- 2} > 0$ .

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Gallager expurgated exponent lower bound

Statement

For every finite unconstrained DMC and rate $R > 0$ , the liminf average- and maximal-error exponents satisfy $E_{a v}^{-} (R) \geq E_{e x} (R), E_{m a x}^{-} (R) \geq E_{e x} (R),$ where $E_{e x}$ is defined in Gallager, random-coding, expurgated, and sphere-packing functions. This is a lower bound; it is not asserted to equal the general reliability function.

Facts & Assumptions

Given: A finite DMC $W$ , a rate $R > 0$ , and the sequence $M_{n} = ⌈ e^{n R} ⌉$ .

[F1]

Finite discrete memoryless channels: for a block input and output, $W^{n} (y^{n} ∣ x^{n}) = \prod_{i} W (y_{i} ∣ x_{i})$ .

[F2]

Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: ML decoding defines a deterministic length- $n$ code, and maximal error is the largest per-message error.

[F3]

Gallager, random-coding, expurgated, and sphere-packing functions: $B (x, x^{'}) = \sum_{y} \sqrt{W (y ∣ x) W (y ∣ x^{'})}$ and $E_{0 x} (ρ, P) = - ρ \ln \sum_{x, x^{'}} P (x) P (x^{'}) B (x, x^{'})^{1 / ρ}$ for $ρ \geq 1$ .

[F4]

Real powers for positive bases, with the zero-base positive-exponent convention, Continuity and derivatives of positive-base real powers, The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents, The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : positive-base real powers have derivative $(t^{r})^{'} = r t^{r - 1}$ and satisfy the power and scaling laws.

[F5]

On an interval $I$ , for $f$ continuous on $I$ and differentiable at every interior point: $f^{'} \geq 0$ throughout gives $f$ nondecreasing, $f^{'} > 0$ gives $f$ increasing, $f^{'} \leq 0$ and $f^{'} < 0$ give the two decreasing forms; conversely a nondecreasing $f$ has $f^{'} \geq 0$ and a nonincreasing $f$ has $f^{'} \leq 0$ wherever it is differentiable, and no strict converse is claimed: a continuous function on an interval with nonnegative interior derivative is nondecreasing, and with nonpositive derivative is nonincreasing.

Proof

1.1F1F2algebra

For any two codewords $x^{n}, x^{' n}$ , if ML decoding selects the competitor when $x^{n}$ was sent, then $W^{n} (y^{n} ∣ x^{' n}) \geq W^{n} (y^{n} ∣ x^{n})$ . On that event $W^{n} (y^{n} ∣ x^{n}) \leq \sqrt{W^{n} (y^{n} ∣ x^{n}) W^{n} (y^{n} ∣ x^{' 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 \neq m} B^{n} (x_{m}^{n}, x_{j}^{n})$ , where $B^{n} (x^{n}, x^{' n}) = \prod_{i} B (x_{i}, x_{i}^{'})$ .

2.1F1F3F4F5step 1.1algebrainduction

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, \infty)$ by [F4], so it is nonincreasing by [F5]. For $t > 0$ , put $g (t) = 1 + t^{r} - (1 + t)^{r}$ ; [F4] gives $g^{'} (t) = r (t^{r - 1} - (1 + t)^{r - 1}) \geq 0$ . Also $t^{r} \to 0$ as $t ↓ 0$ : its derivative is positive, and for any $η > 0$ , $0 < t < η^{1 / r}$ gives $t^{r} < η$ by [F4]–[F5]. Thus $g$ extends continuously to $g (0) = 0$ . By [F5] on $[0, \infty)$ , $g (t) \geq 0$ for all $t \geq 0$ . If $a > 0$ , scale with $t = b / a$ and use [F4] to obtain $(a + b)^{r} \leq a^{r} + b^{r}$ ; if $a = 0$ , equality holds, including $a = b = 0$ . Induction gives $(\sum_{j} a_{j})^{r} \leq \sum_{j} a_{j}^{r}$ for every finite nonnegative family (the empty family gives $0 = 0$ ). Now draw $M^{'}$ codewords independently from $P^{n}$ and take $r = 1 / ρ$ for $ρ \geq 1$ . The proved finite-sum inequality and step 1.1 yield $E f_{m}^{1 / ρ} \leq \sum_{j \neq m} E B^{n} (X_{m}^{n}, X_{j}^{n})^{1 / ρ} = (M^{'} - 1) {(\sum_{x, x^{'}} P (x) P (x^{'}) B (x, x^{'})^{1 / ρ})}^{n} .$ The equality follows from independent coordinates, the product form of $B^{n}$ , and the power laws in [F4].

3.1F2step 2.1

Averaging [2.1] over messages and codebooks gives a codebook with $M^{' - 1} \sum_{m} f_{m}^{1 / ρ} \leq (M^{'} - 1) z^{n}$ , where $z = \sum_{x, x^{'}} P (x) P (x^{'}) B (x, x^{'})^{1 / ρ}$ . At least $M^{'} / 2$ messages satisfy $f_{m}^{1 / ρ} \leq 2 (M^{'} - 1) z^{n}$ ; otherwise their sum would exceed $M^{'} (M^{'} - 1) z^{n}$ . Restrict the code to $M^{'} / 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^{'} - 1) z^{n}]^{ρ}$ .

4.1F2F3step 3.1∎

Set $M^{'} = 2 M_{n}$ , retain exactly $M_{n}$ messages, and take $- n^{- 1} \ln$ of the bound in step 3.1. Since $n^{- 1} \ln (M^{'} - 1) \to R$ , this gives $E_{m a x}^{-} (R) \geq - ρ \ln z - ρ R = E_{0 x} (ρ, P) - ρ R$ . Optimizing over $P$ and $ρ \geq 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.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Gallager random-coding exponent lower bound

Statement

For every finite DMC without an input-cost constraint or feedback and every $R > 0$ , $E_{a v}^{-} (R) \geq E_{r} (R), E_{m a x}^{-} (R) \geq E_{r} (R),$ where $E_{r}$ is the random-coding function in Gallager, random-coding, expurgated, and sphere-packing functions. If $0 < R < C (W)$ , then $E_{r} (R) > 0$ . This is an achievability lower bound, not an exact general reliability formula.

Facts & Assumptions

Given: A finite DMC $W$ , rate $R > 0$ , the fixed-size sequence $M_{n} = ⌈ e^{n R} ⌉$ , and the error-exponent definitions.

[F1]

Finite discrete memoryless channels and Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: a length- $n$ code uses the product channel, a deterministic encoder/decoder, and uniform-message average and maximal errors.

[F2]

Gallager, random-coding, expurgated, and sphere-packing functions: $E_{0} (ρ, P) = - \ln \sum_{y} (\sum_{x} P (x) W (y ∣ x)^{1 / (1 + ρ)})^{1 + ρ}$ for $ρ \geq 0$ , and $E_{r} (R) = \sup_{0 \leq ρ \leq 1} (\max_{P} E_{0} (ρ, P) - ρ R)$ .

[F3]

Finite Jensen inequality for a convex function and nonnegative weights summing to one and Convex, strictly convex, concave, strictly concave, and midpoint-convex real functions on an interval: a convex function of a finite probability-weighted mean is at most the weighted mean of its values; a function is concave exactly when its negative is convex.

[F4]

Expurgation converts small average error to small maximal error: a code of average error $a$ has a subcode with at least half its messages and maximal error at most $2 a$ .

[F5]

Finite mutual information and Single-letter information capacity of a finite DMC: $I (P, W)$ is the finite joint/product KL sum in nats, and $C (W) = \max_{P} I (P, W)$ .

[F6]

Finite DMC information capacity is attained: some input law $P^{*}$ satisfies $I (P^{*}, W) = C (W)$ .

[F7]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : logarithmic differentiation and the product rule apply on positive arguments.

[F8]

Real powers for positive bases, with the zero-base positive-exponent convention, Continuity and derivatives of positive-base real powers, and The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ : for fixed $w > 0$ , $w^{a} = \exp (a \ln w)$ and the chain rule differentiates powers with a variable real exponent; the convention $0^{a} = 0$ for $a > 0$ makes a zero-transition term identically zero near $ρ = 0$ .

[F9]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is continuous on $(0, \infty)$ .

[F10]

[F11]

The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents and On an interval $I$ , for $f$ continuous on $I$ and differentiable at every interior point: $f^{'} \geq 0$ throughout gives $f$ nondecreasing, $f^{'} > 0$ gives $f$ increasing, $f^{'} \leq 0$ and $f^{'} < 0$ give the two decreasing forms; conversely a nondecreasing $f$ has $f^{'} \geq 0$ and a nonincreasing $f$ has $f^{'} \leq 0$ wherever it is differentiable, and no strict converse is claimed: positive-base powers satisfy $(t^{a})^{b} = t^{a b}$ , and a positive derivative makes a continuous function increasing on an interval.

Proof

1.1F1givenalgebra

Fix $0 < ρ \leq 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} ∣ x_{m}^{n}) > 0$ , an error implies some competitor has likelihood at least the true likelihood. Hence its error indicator is at most ${(\sum_{j \neq m} {[\frac{W^{n} (y^{n} ∣ x_{j}^{n})}{W^{n} (y^{n} ∣ x_{m}^{n})}]}^{1 / (1 + ρ)})}^{ρ},$ which is at least one on every error event; outputs of zero true likelihood carry no channel mass.

1.2F2F5F7F8given

For fixed $P$ , write $A_{y} (ρ) = \sum_{x} P (x) W (y ∣ x)^{1 / (1 + ρ)}$ and $S (ρ) = \sum_{y} A_{y} (ρ)^{1 + ρ}$ . If $W (y ∣ x) > 0$ , [F7]–[F8] and the chain rule give ${\frac{d}{d ρ} W (y ∣ x)^{1 / (1 + ρ)} ∣}_{ρ = 0} = - W (y ∣ x) \ln W (y ∣ x)$ ; if $W (y ∣ x) = 0$ , that term is identically zero. Thus, for $q_{y} = A_{y} (0) = (P W) (y) > 0$ , $A_{y}^{'} (0) = - \sum_{x : W (y ∣ x) > 0} P (x) W (y ∣ x) \ln W (y ∣ x) .$ On a neighborhood of $0$ where $A_{y} (ρ) > 0$ , write $A_{y} (ρ)^{1 + ρ} = \exp ((1 + ρ) \ln A_{y} (ρ))$ . By [F7]–[F8] and the product and chain rules, its derivative at zero is $q_{y} \ln q_{y} + A_{y}^{'} (0)$ . If $q_{y} = 0$ , every $P (x) W (y ∣ x) = 0$ , so $A_{y} (ρ) = 0$ for all $ρ \geq 0$ and its outer term vanishes identically. Summing the finite terms gives $S^{'} (0) = \sum_{y : q_{y} > 0} q_{y} \ln q_{y} - \sum_{x, y : P (x) W (y ∣ x) > 0} P (x) W (y ∣ x) \ln W (y ∣ x) = - I (P, W),$ because [F5] expands $I (P, W) = \sum_{x, y : P W > 0} P (x) W (y ∣ x) \ln \frac{W (y ∣ x)}{q_{y}}$ . Since $S (0) = 1$ and $E_{0} (ρ, P) = - \ln S (ρ)$ , the right derivative is $\partial_{ρ} E_{0} (0, P) = I (P, W)$ .

1.3F3F8F10F11givenalgebra

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

2.1F1F3step 1.1step 1.3algebra

Conditional on $x_{m}^{n}, y^{n}$ , the power Jensen inequality from step 1.3 bounds the expected $ρ$ -power by the $ρ$ -power of its mean. Independence of each competitor gives that mean as $(M - 1) \frac{A_{n} (y^{n})}{W^{n} (y^{n} ∣ x_{m}^{n})^{1 / (1 + ρ)}}, A_{n} (y^{n}) : = \sum_{x^{n}} P^{n} (x^{n}) W^{n} (y^{n} ∣ x^{n})^{1 / (1 + ρ)} .$ Multiplication by the true likelihood changes its power to $1 - ρ / (1 + ρ) = 1 / (1 + ρ)$ . Averaging over the transmitted word and summing over outputs therefore bounds ensemble average error by $(M - 1)^{ρ} \sum_{y^{n}} A_{n} (y^{n})^{1 + ρ} .$

3.1F1F2step 2.1algebra

The product law in [F1] makes $A_{n} (y^{n}) = \prod_{i = 1}^{n} \sum_{x} P (x) W (y_{i} ∣ x)^{1 / (1 + ρ)}$ . Thus the sum in step 2.1 factors into the $n$ th power of the single-letter sum defining $E_{0} (ρ, P)$ in [F2]. Some deterministic codebook has average error at most its ensemble mean, so for each $n$ a code exists with $ϵ_{a v} \leq \exp {- n [E_{0} (ρ, P) - ρ n^{- 1} \ln (M - 1)]} .$

4.1F2F6F8F9step 3.1

With $M_{n} = ⌈ e^{n R} ⌉$ , one has $n^{- 1} \ln (M_{n} - 1) \to R$ . Taking the liminf exponent in step 3.1 and optimizing over $P$ and $0 < ρ \leq 1$ gives the corresponding positive-parameter supremum. For a capacity-achieving $P^{*}$ from [F6], each $A_{y} (ρ)$ tends to $q_{y} = (P^{*} W) (y)$ as $ρ ↓ 0$ . If $q_{y} > 0$ , then $A_{y} (ρ)^{1 + ρ} = \exp ((1 + ρ) \ln A_{y} (ρ)) \to q_{y}$ ; if $q_{y} = 0$ , all $P^{*} (x) W (y ∣ x) = 0$ and that term is identically zero. Hence $S (ρ) \to \sum_{y} q_{y} = 1$ and $E_{0} (ρ, P^{*}) = - \ln S (ρ) \to 0$ by [F9]. Since $E_{0} (ρ) \geq E_{0} (ρ, P^{*})$ , the positive-parameter supremum is at least $\lim_{ρ ↓ 0} (E_{0} (ρ, P^{*}) - ρ R) = 0$ . The added endpoint $ρ = 0$ has value zero, so it does not change the supremum, which is $E_{r} (R)$ .

5.1F1F4step 4.1algebra

Apply the same bound at size $2 M_{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 (2 M_{n}) - R \to 0$ do not change the liminf exponent. Hence $E_{m a x}^{-} (R) \geq E_{r} (R)$ .

6.1F2F5step 1.2∎

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

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Sphere-packing converse above the finite-divergence threshold

Statement

Assume the Axiom of Choice and Countable Choice. Let $W$ be a finite unconstrained DMC. For $P$ on $X$ , let $V$ range over row-stochastic channels satisfying $supp V (\cdot ∣ x) \subseteq supp W (\cdot ∣ x)$ , and define $D_{P} (V) = \sum_{x} P (x) D (V (\cdot ∣ x) ∥ W (\cdot ∣ x)), I_{P} (V) = I (X; Y) under P (x) V (y ∣ x),$ $J (P) = \min_{V} I_{P} (V), R_{\infty} (W) = \max_{P} J (P) .$ For every $R > R_{\infty} (W)$ , the limsup average- and maximal-error exponents satisfy $E_{a v}^{+} (R) \leq E_{s p} (R), E_{m a x}^{+} (R) \leq E_{s p} (R),$ where $E_{s p}$ is defined in Gallager, random-coding, expurgated, and sphere-packing functions. The theorem makes no endpoint assertion at $R = R_{\infty} (W)$ .

Facts & Assumptions

Given: The finite DMC, deterministic length- $n$ codes, and the two choice principles in the Statement.

[A1]

The Axiom of Choice and The Axiom of Countable Choice ( ${A C}_{ω}$ ): AC and Countable Choice are assumed only for the weak-separation application in step 3.2.

[F1]

Finite discrete memoryless channels and The DMC product laws are stochastic kernels: the DMC block law is the product of its row kernels.

[F2]

Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: messages are uniform, codewords are deterministic, and average error is the average of message errors.

[F3]

Finite-alphabet Fano inequality: for a uniform $M \geq 2$ -message variable and any deterministic decoder with error $e$ , $I (M; Y) \geq (1 - e) \ln M - \ln 2$ .

[F4]

Finite entropy and mutual-information chain rules and Finite KL divergence is nonnegative with equality exactly at equal laws: finite entropy obeys the chain rule, and finite mutual information/conditional mutual information are nonnegative.

[F5]

Finite mutual information and Finite distributions, entropy, divergence, and stochastic matrices: mutual information is finite KL, and entropy is $H (p) = - \sum_{p_{i} > 0} p_{i} \ln p_{i}$ with $0 \ln 0 = 0$ .

[F6]

Finite log-sum inequality with support and equality cases: the finite log-sum inequality proves joint convexity of KL under linear mixing of both arguments.

[F7]

Heine-Cantor: a continuous map from a compact metric space to any metric space is uniformly continuous and For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: continuous functions on compact metric subsets of Euclidean space are uniformly continuous and attain extrema.

[F8]

Disjoint nonempty Euclidean convex sets have a separating hyperplane: under AC and Countable Choice, disjoint nonempty convex subsets of Euclidean space admit a nonzero weak separating normal.

[F9]

Globally optimized constant-composition and Gallager functions agree: for every $ρ > 0$ , $\max_{P} E_{0, c c} (ρ, P) = \max_{P} E_{0} (ρ, P)$ .

[F10]

Finite Jensen inequality for a convex function and nonnegative weights summing to one: a finite weighted average of a concave function is at most that function of the weighted average.

[F11]

Average and maximal error reliability exponents and Gallager, random-coding, expurgated, and sphere-packing functions: $E_{a v}^{+}, E_{m a x}^{+}$ are limsup error exponents and $E_{s p} (R) = \sup_{ρ \geq 0} (\max_{P} E_{0} (ρ, P) - ρ R)$ .

[F12]

The logarithm grows more slowly than every positive real power: $t \ln t \to 0$ as $t ↓ 0$ , and $\ln (n + 1) / n \to 0$ .

[F13]

Finite-channel mutual information is concave in the input law: for every finite channel $V$ , $P \mapsto I_{P} (V)$ is concave, including on the boundary of the input simplex.

Proof

1.1F1F4F5F7F12given

The allowed $V$ form a compact product of row simplexes. For fixed $P$ , $I_{P} (V)$ and $D_{P} (V)$ are continuous in $V$ : finite sums use $t \ln t \to 0$ at zero by [F12], and every denominator $W (y ∣ x)$ charged by $V$ is a fixed positive transition. Thus $J (P) = \min_{V} I_{P} (V)$ exists. The joint map $(P, V) \mapsto I_{P} (V)$ is continuous on the compact product of the input simplex and the allowed-channel set; [F7] makes it uniformly continuous. Therefore $∣ J (P) - J (P^{'}) ∣ \leq \sup_{V} ∣ I_{P} (V) - I_{P^{'}} (V) ∣ \to 0$ as $P^{'} \to P$ . The continuous $J$ attains its finite maximum $R_{\infty}$ by [F7]. Since finite mutual information is nonnegative by [F4], $J (P) \geq 0$ and $R_{\infty} \geq 0$ . Since $R > R_{\infty}$ , for every $P$ its minimizing channel $V_{0}$ satisfies $I_{P} (V_{0}) = J (P) < R$ .

1.2F1F3F4F5F10F12F13givenalgebra

Consider any deterministic $M \geq 2$ message code whose every codeword has type $P$ , and evaluate its average error $e_{V}$ through the product channel $V^{n}$ . Let $U$ be its uniform message and $X^{n}$ its codeword. Since $X^{n}$ is a function of $U$ and the channel depends on $U$ only through $X^{n}$ , $I (U; Y^{n}) = H (Y^{n}) - H (Y^{n} ∣ U)$ . The finite entropy chain rule and nonnegative conditional mutual information in [F4] give $H (Y^{n}) \leq \sum_{i} H (Y_{i})$ . The product-channel law in [F1] gives $H (Y^{n} ∣ U) = \sum_{i} H (Y_{i} ∣ X_{i})$ , so $I (U; Y^{n}) \leq \sum_{i} I (X_{i}; Y_{i}) = \sum_{i} I_{P_{i}} (V)$ , where $P_{i}$ is the law of $X_{i}$ under the uniform message. Every codeword has type $P$ , hence $n^{- 1} \sum_{i} P_{i} = P$ . Concavity [F13] and finite Jensen [F10] imply $I (U; Y^{n}) \leq n I_{P} (V)$ . Fano's inequality [F3] now yields $e_{V} \geq 1 - \frac{n I_{P} (V) + \ln 2}{\ln M} .$ The entropy formula [F5] and limit [F12] also show that $P \mapsto I_{P} (V)$ is continuous, as needed when types vary.

2.1F5F6step 1.1

For fixed $P$ , the closed feasible set ${V : I_{P} (V) \leq R}$ is nonempty and compact, so $S_{P} (R) : = \min_{I_{P} (V) \leq R} D_{P} (V)$ exists. The open infimum over $I_{P} (V) < R$ equals this minimum: if $V^{*}$ minimizes the closed problem, mix it with the strict witness $V_{0}$ from step 1.1. Convexity of $I_{P}$ gives $I_{P} ((1 - t) V^{*} + t V_{0}) < R$ for $t > 0$ , while continuity gives $D_{P} ((1 - t) V^{*} + t V_{0}) \to S_{P} (R)$ . For $D_{P}$ , [F6] gives convexity row by row and then after the finite $P$ -weighted sum. For $I_{P}$ , write it as $D (P V_{X Y} ∥ P \otimes P V_{Y})$ ; both arguments are the same convex mixtures when $V$ is mixed, so [F6] gives convexity. This proves the required convexity and continuity facts.

2.2F1F2step 1.2

For each row $x$ , under $V (\cdot ∣ x)$ the log ratio $\ln [V (Y ∣ x) / W (Y ∣ x)]$ has mean $D (V_{x} ∥ W_{x})$ and variance bounded uniformly over allowed $V$ : the finite set of positive $W (y ∣ x)$ has a positive minimum, and $t (\ln (t / W (y ∣ x)))^{2}$ extends continuously at $t = 0$ . Thus for some finite $K_{W}$ , a codeword of type $P_{n}$ has log ratio $L = \ln [V^{n} (Y^{n} ∣ x^{n}) / W^{n} (Y^{n} ∣ x^{n})]$ with mean $n D_{P_{n}} (V)$ and variance at most $n K_{W}$ . On $L > n (D_{P_{n}} (V) + η)$ , the squared centered deviation exceeds $n^{2} η^{2}$ , so the event indicator is at most $(L - E L)^{2} / (n^{2} η^{2})$ . Taking expectations gives $V^{n} {L > n (D_{P_{n}} (V) + η)} \leq K_{W} / (n η^{2})$ . On its complement $W^{n} \geq e^{- n (D_{P_{n}} (V) + η)} V^{n}$ ; integrating over decoder error events gives $e_{W} \geq e^{- n (D_{P_{n}} (V) + η)} (e_{V} - \frac{K_{W}}{n η^{2}}) .$

3.1F1F2F3F11F12step 1.1step 1.2step 2.1step 2.2

At each $n$ , choose a code attaining the finite-block minimum average error. For any such code of size $M_{n}$ , partition its messages into input types; there are at most $(n + 1)^{∣ X ∣}$ types. Restrict to a largest type class of size $M_{n}^{'} \geq M_{n} / (n + 1)^{∣ X ∣}$ . Reindex the retained messages and map every old decoder output outside the retained class to one fixed retained message. For each retained message this decoder cannot increase its error, so if $e_{n}$ is the original average error and $e_{n}^{'}$ the restricted one, then $e_{n} \geq (M_{n}^{'} / M_{n}) e_{n}^{'}$ . Since $M_{n} = ⌈ e^{n R} ⌉$ and $R > 0$ by step 1.1, $M_{n}^{'}$ grows exponentially and $n^{- 1} \ln M_{n}^{'} \to R$ by [F12]. Along any subsequence realizing the limsup exponent, compactness gives a further subsequence of selected types $P_{n} \to P$ . For each allowed $V$ with $I_{P} (V) < R$ , continuity from step 1.2 makes its Fano lower bound bounded away from zero; step 2.2 then gives $lim sup - n^{- 1} \ln e_{n} \leq D_{P} (V) + η$ , since the type-class factor costs only $∣ X ∣ \ln (n + 1) / n$ . Letting $η ↓ 0$ and taking the infimum over strict-feasible $V$ proves $E_{a v}^{+} (R) \leq \sup_{P} \inf_{V : I_{P} (V) < R} D_{P} (V) = \sup_{P} S_{P} (R),$ where the equality is step 2.1. Since every code's maximal error is at least its average error, $P_{m a x}^{*} (n, M_{n}) \geq P_{a v}^{*} (n, M_{n})$ and the same upper bound holds for $E_{m a x}^{+}$ .

3.2A1F8step 1.1step 2.1algebra

Fix $P$ . Form the upper image $G = {(a, b) : a \geq I_{P} (V), b \geq D_{P} (V) for some allowed V}$ and the open convex set $O = (- \infty, R) \times (- \infty, S_{P} (R))$ . They are nonempty convex sets. If a point lay in both, its witnessing $V$ would satisfy $I_{P} (V) < R$ and $D_{P} (V) < S_{P} (R)$ , contradicting the definition of the closed minimum; hence they are disjoint. Convexity of $G$ follows from step 2.1. Apply [F8] under [A1] to obtain a nonzero normal separating $G$ from $O$ . Because $G$ is upper in each coordinate, the separating normal in the orientation $a \cdot g \leq a \cdot o$ must have nonpositive coordinates (otherwise increasing that coordinate of $g$ violates separation). Reversing its sign gives weights $u, v \geq 0$ , not both zero, with $u I_{P} (V) + v D_{P} (V) \geq u R + v S_{P} (R) for every allowed V .$ Strict feasibility from step 1.1 forces $v > 0$ : if $v = 0$ , then $u > 0$ and the inequality contradicts $I_{P} (V_{0}) < R$ . Normalize $v = 1$ and put $ρ = u / v \geq 0$ .

4.1step 2.1step 3.2algebra

The separator gives $\inf_{V} {D_{P} (V) + ρ I_{P} (V)} - ρ R \geq S_{P} (R)$ . Conversely, a minimizer $V^{*}$ of the closed problem has $I_{P} (V^{*}) \leq R$ and $D_{P} (V^{*}) = S_{P} (R)$ , so for every $ρ \geq 0$ , $\inf_{V} {D_{P} (V) + ρ I_{P} (V)} - ρ R \leq S_{P} (R) .$ Thus strict feasibility proves the exact dual identity $S_{P} (R) = \sup_{ρ \geq 0} {E_{0, c c} (ρ, P) - ρ R},$ with $E_{0, c c} (0, P) = 0$ .

5.1F9F11step 2.1step 3.1step 4.1cases∎

Taking suprema over $P$ and $ρ$ in step 4.1, interchanging two suprema, and applying [F9] for $ρ > 0$ (at $ρ = 0$ both optimized quantities are zero) gives $\sup_{P} S_{P} (R) = \sup_{ρ \geq 0} {\max_{P} E_{0} (ρ, P) - ρ R} = E_{s p} (R) .$ Combining with step 3.1 proves both stated converses. The strict condition $R > R_{\infty}$ was used in steps 1.1, 2.1, and 4.1; no endpoint conclusion follows from this proof.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Nondegenerate normal approximation for finite unconstrained DMCs

Statement

Assume the Axiom of Choice. Let $W$ be a fixed finite DMC with no feedback or input-cost constraint, let $0 < ϵ < 1 / 2$ be fixed, and suppose $V_{\min} (W) > 0$ . For $k \in {a v, m a x}$ , let $M_{k}^{*} (n, ϵ)$ be the largest number of messages in a deterministic length- $n$ code with uniform messages and error criterion $k$ at most $ϵ$ . Then $\ln M_{k}^{*} (n, ϵ) = n C (W) + \sqrt{n V_{\min} (W)} Φ^{- 1} (ϵ) + O (\ln n), k \in {a v, m a x},$ where all logarithms are natural, $Φ$ is the standard-normal CDF, and the constants may depend on $W, ϵ$ . This theorem makes no claim for cost constraints, $ϵ \geq 1 / 2$ , zero dispersion, or a third-order coefficient.

Facts & Assumptions

Given: A finite unconstrained DMC $W$ , a fixed $0 < ϵ < 1 / 2$ , and $V_{\min} (W) > 0$ .

[A1]

The Axiom of Choice: the Axiom of Choice is assumed through the standard-normal law and the Berry–Esseen supplier.

[F1]

Finite discrete memoryless channels and The DMC product laws are stochastic kernels: $W^{n} (y^{n} ∣ x^{n}) = \prod_{i} W (y_{i} ∣ x_{i})$ is the DMC block law.

[F2]

Finite DMC information capacity is attained and Single-letter information capacity of a finite DMC: $C (W) = \max_{P} I (P, W)$ is finite and attained; the CAID set $Π (W)$ is nonempty.

[F3]

The capacity-achieving output law is unique and Capacity-achieving output laws bound every row divergence: all CAIDs induce a common output law $Q^{*}$ , every channel row is supported on $Q^{*}$ , and $D (W_{x} ∥ Q^{*}) \leq C (W)$ .

[F4]

DMC minimum and maximum dispersion are attained and Conditional information variance and DMC dispersion: $V_{\min} (W)$ is attained on $Π (W)$ and $V (P, W)$ is the conditional information variance.

[F5]

A CAID's information-density variance equals its conditional dispersion: for every CAID, the conditional information-density mean is $C (W)$ on each positive-mass input and the unconditional information-density variance equals its conditional dispersion.

[F6]

Finite-DMC information deficit controls squared distance to the CAID set: $C (W) - I (P, W) \geq α {dist}_{2} (P, Π (W))^{2}$ for some $α > 0$ and every input law $P$ .

[F7]

Berry–Esseen bound for a finite independent array: for independent finite-support summands with total variance $σ^{2} > 0$ , the CDF error from $Φ$ is at most $1088 \sum_{i} E ∣ X_{i} ∣^{3} / σ^{3}$ .

[F8]

Finite-DMC dependence-testing achievability bound: a deterministic code exists with average error at most $E e^{- [ı (X^{n}; Y^{n}) - \ln ((M - 1) / 2)]_{+}}$ for $M \geq 2$ .

[F9]

Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: the encoder and decoder are deterministic; decoder regions are disjoint; average and maximal error are the uniform-message average and largest message error.

[F10]

Standard normal and normal laws and The standard normal CDF has unique symmetric quantiles: $Φ$ is continuous and strictly increasing from $0$ to $1$ , with a unique inverse quantile at each $ϵ \in (0, 1)$ .

[F11]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , and The logarithm grows more slowly than every positive real power: finite log formulas are smooth when their denominators stay positive and $t (\ln t)^{2}$ extends continuously to zero.

[F12]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ and The first fundamental theorem: if $f$ is integrable on $[a, b]$ and continuous at $c$ , then $F^{'} (c) = f (c)$ ; in particular a continuous $f$ has $F$ as a primitive: a differentiable scalar function changes by its derivative at an intermediate point times the interval length; the standard normal CDF has derivative $φ$ and differences are integrals of that density.

[F13]

For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: the finite input simplex is compact, and its closed subsets are compact.

[F14]

Finite mutual information and Finite distributions, entropy, divergence, and stochastic matrices: mutual information is the finite joint/product KL sum and finite entropy is a sum of $- t \ln t$ terms with $0 \ln 0 = 0$ .

Proof

1.1F2F3F5given

Choose any CAID and let $Q^{*}$ be its output law. By [F3], every row is supported on $Q^{*}$ and has divergence $d_{x} : = D (W_{x} ∥ Q^{*}) \leq C (W)$ . For every CAID $P$ , [F5] gives $E [ı_{P} (X; Y) ∣ X = x] = C (W)$ on each positive-mass input and $Var (ı_{P} (X; Y)) = V (P, W)$ .

1.2F2F4F11F12F13F14algebra

By [F13] the input simplex is compact. Expanding the finite KL definition [F14] gives $I (P, W) = H (P W) - \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 $Π (W)$ is closed and therefore compact; [F2], [F4] supply a minimum-dispersion CAID. Since $Q^{*}$ is positive on every globally reachable output, choose $U = {P \in Δ_{X} : {dist}_{2} (P, Π (W)) < δ}$ with compact closure in the input simplex and with every $(P W) (y)$ on that support bounded below by a positive constant on $\overline{U}$ . On the support of each row define $ℓ_{P} (x; y) : = \ln [W (y ∣ x) / (P W) (y)]$ ; it is finite on $U$ and agrees with $ı_{P} (x; y)$ whenever $P (x) > 0$ . Define $T (P, W) : = \sum_{x : P (x) > 0} P (x) E_{W_{x}} ∣ ℓ_{P} (x; Y) - D (W_{x} ∥ P W) ∣^{3}$ , omitting zero-weight rows. The local extensions of $V$ and $T$ are respectively $\sum_{x} P (x) {Var}_{W_{x}} ℓ_{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 $\overline{U}$ , and $u \mapsto ∣ u ∣^{3}$ has continuous derivative $3 u ∣ u ∣$ . Their first derivatives are bounded on compact $\overline{U}$ . Since $V \geq V_{\min} > 0$ on $Π (W)$ , shrink $δ$ so that $V \geq v_{0} > 0$ on $\overline{U}$ , and let $T_{0}$ bound $T$ there. The segment from any $P \in U$ to a nearest $P_{0} \in Π (W)$ stays in $U$ ; the mean-value theorem then gives $∣ \sqrt{V (P, W)} - \sqrt{V (P_{0}, W)} ∣ \leq L ∥ P - P_{0} ∥_{2}$ for one finite $L$ .

1.3F1F2givenalgebra

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

1.4F1F9givenalgebra

Fix a code whose every codeword has type $P$ and let $Q_{n} = (P W)^{n}$ . For message $m$ with codeword $x_{m}^{n}$ , put $L_{m} (y^{n}) = \ln [W^{n} (y^{n} ∣ x_{m}^{n}) / 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 $n I (P, W)$ and variance $n V (P, W)$ ; the summands are independent and row counts are $n P (x)$ . For any $γ > 0$ , split each decoder region at $t = \ln M - γ$ . On $L_{m} \leq t$ , $W^{n} (y^{n} ∣ x_{m}^{n}) \leq M e^{- γ} Q_{n} (y^{n})$ . Averaging over messages and using disjoint decoder regions gives $1 - e_{a v} \leq \Pr {L > \ln M - γ} + e^{- γ}, F_{L} (\ln M - γ) \leq e_{a v} + e^{- γ} .$

2.1A1F7F9F10step 1.2step 1.4algebra

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} ∣ F_{L} (n I (P, W) + \sqrt{n V (P, W)} z) - Φ (z) ∣ \leq B_{0} / \sqrt{n},$ where $B_{0} = 1088 T_{0} / v_{0}^{3 / 2}$ . If $e_{a v} \leq ϵ + n^{- 1 / 2}$ and $γ = \frac{1}{2} \ln n$ , step 1.4 yields $Φ ⁣ (\frac{\ln M - γ - n I (P, W)}{\sqrt{n V (P, W)}}) \leq ϵ + (B_{0} + 2) n^{- 1 / 2} .$ Since $ϵ$ is fixed in $(0, 1)$ , choose a compact interval about $z_{ϵ}$ on which the positive density $φ$ has lower bound $m > 0$ . The mean-value theorem [F12] gives $∣ Φ (u) - Φ (v) ∣ \geq m ∣ u - v ∣$ there, so the inverse is locally Lipschitz at $ϵ$ . Hence, uniformly for such types, $\ln M \leq n I (P, W) + \sqrt{n V (P, W)} z_{ϵ} + \frac{1}{2} \ln n + O (1), z_{ϵ} : = Φ^{- 1} (ϵ) .$

2.2F1F9step 1.3step 1.4

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

2.3F4F5F7F8step 1.1algebra

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

3.1F4F6step 1.2step 2.1algebra

Put $a = - z_{ϵ} > 0$ and $d = {dist}_{2} (P, Π (W))$ . For $P \in U$ , choose a nearest $P_{0} \in Π (W)$ , so $V (P_{0}, W) \geq V_{\min}$ . By [F6] and step 1.2, $n I (P, W) - a \sqrt{n V (P, W)} \leq n C - a \sqrt{n V_{\min}} - n α d^{2} + a L \sqrt{n} d \leq n C - a \sqrt{n V_{\min}} + \frac{a^{2} L^{2}}{4 α} .$ Together with step 2.1 this gives the desired $n C + \sqrt{n V_{\min}} z_{ϵ} + O (\ln n)$ upper bound for nearby constant-composition codes.

3.2F7F8F10F12step 2.3given

Set $u_{n} = ϵ - (1088 T^{*} / V_{\min}^{} + 2) n^{- 1 / 2}$ and $t_{n} = n C + \sqrt{n V_{\min}} Φ^{- 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 + ⌊ 2 e^{t_{n} - γ} ⌋$ , which is at least two for large $n$ and satisfies $t \leq t_{n}$ and $\ln M \geq t_{n} - γ - O (1)$ . Step 2.3 and [F7] give a deterministic code with average error at most $ϵ - n^{- 1 / 2}$ and $\ln M \geq n C + \sqrt{n V_{\min}} z_{ϵ} - O (\ln n),$ using local Lipschitz continuity of $Φ^{- 1}$ at $ϵ$ from [F12].

4.1F9step 2.1step 2.2step 3.1

For an arbitrary code of size $M$ with individual errors $e_{m} \geq 0$ and average error at most $ϵ$ , put $τ = ϵ + n^{- 1 / 2}$ and let $b$ count the messages with $e_{m} > τ$ . If $b > 0$ , then $b τ < \sum_{e_{m} > τ} e_{m} \leq \sum_{m} e_{m} \leq M ϵ$ , so the retained count $g = M - b$ satisfies $g > M (1 - ϵ / τ) = M / (1 + ϵ \sqrt{n})$ . If $b = 0$ , then $g = M$ satisfies the same weak lower bound. Hence in all cases $g \geq ⌈ M / (1 + ϵ \sqrt{n}) ⌉ \geq 1$ , and every retained message has error at most $τ$ . 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)^{∣ X ∣}$ input types, one type subcode has at least $⌈ g / K ⌉$ messages, hence at least $M / [(1 + ϵ \sqrt{n}) K]$ . Its logarithmic size loss is therefore at most $\ln (1 + ϵ \sqrt{n}) + ∣ X ∣ \ln (n + 1) = O (\ln n)$ and its average error is at most $ϵ + n^{- 1 / 2}$ . Applying steps 2.1, 2.2, and 3.1 to this type subcode gives $\ln M \leq n C + \sqrt{n V_{\min}} z_{ϵ} + O (\ln n) .$

5.1F9step 4.1algebra

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 $∣ Y ∣^{n} / M$ , since each output is decoded as only one message and contributes at most one to the sum of message success probabilities. Thus $M \leq ∣ Y ∣^{n} / (1 - ϵ)$ for either criterion.

6.1F9step 3.2step 4.1step 5.1algebra∎

For all sufficiently large $n$ with $n^{- 1 / 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} \leq \sum_{m} e_{m} \leq M (ϵ - n^{- 1 / 2})$ , so its retained count $g = M - b$ satisfies $g > M / (ϵ \sqrt{n})$ . If $b = 0$ , $g = M \geq M / (ϵ \sqrt{n})$ because $ϵ \sqrt{n} > 1$ . Therefore $g \geq ⌈ M / (ϵ \sqrt{n}) ⌉ \geq 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.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

The error exponent is zero above finite-DMC capacity

Statement

For every finite unconstrained DMC and every $R > C (W)$ , $E_{a v}^{-} (R) = E_{a v}^{+} (R) = E_{m a x}^{-} (R) = E_{m a x}^{+} (R) = 0.$ These are error-probability exponents; no success-probability exponent is asserted.

Facts & Assumptions

Given: A finite DMC $W$ , $R > C (W)$ , and $M_{n} = ⌈ e^{n R} ⌉$ .

[F1]

Strong converse for finite-alphabet DMCs and Average and maximal error of a fixed-length code: for any code sequence with liminf rate above $C (W)$ , average success tends to zero, so both average and maximal errors tend to one; the two criteria are the uniform-message average and largest message error.

[F2]

Average and maximal error reliability exponents: $E_{k}^{\pm} (R)$ are the liminf and limsup of $- n^{- 1} \ln P_{k}^{*} (n, M_{n})$ , with $- \ln 0 = + \infty$ .

[F3]

Average and maximal error of a fixed-length code: maximal error is at least average error for every code.

Proof

1.1F1F2given

For each $n$ , choose a code attaining $P_{a v}^{*} (n, M_{n})$ ; the finite code space makes such a minimizer exist. Its rate is $n^{- 1} \ln M_{n} \to R > C (W)$ , so [F1] implies $P_{a v}^{*} (n, M_{n}) \to 1$ .

1.2F1F2F3givenalgebra

Choose likewise a code attaining $P_{m a x}^{*} (n, M_{n})$ . Its average error is no larger than its maximal error, and [F1] forces its average error to tend to one. Therefore its maximal error, bounded above by one and below by that average error, also tends to one; hence $P_{m a x}^{*} (n, M_{n}) \to 1$ .

2.1F2step 1.1step 1.2∎

If $p_{n} \to 1$ with $0 < p_{n} \leq 1$ eventually, then $- \ln p_{n} \to 0$ and $n^{- 1} (- \ln p_{n}) \to 0$ . Applying this to both optimal error sequences from steps 1.1 and 1.2 makes their liminf and limsup exponents all zero.

5 · Examples, counterexamples and false statements

None yet.