Discrete Memoryless Channel Capacity

Fix $x^n\in {\mathcal{X}}^n$. By [F1] and [F2], each product $W^n(y^n\mid x^n)$ is nonnegative.

Summing over the finite product alphabet and factoring the finite sum gives ${\sum }_{y^n\in {\mathcal{Y}}^n}{W}^n(y^n\mid x^n)={\prod }_{i=1}^n({\sum }_{y_i\in \mathcal{Y}}W(y_i\mid x_i))={\prod }_{i=1}^{n}1=1$. Together with step 1.1, these are exactly the stochastic-kernel conditions.

For an input law $P_X$, let $Q_{P_X}=P_{X}W$. By [F2] and [F3], $I(P_X;W)=H(Q_{P_X})-{\sum }_x{P}_X(x)H(W(\cdot \mid x))$. The second term is linear in $P_X$.

The scalar summand $-t\ln t$, extended by $0$ at $t=0$, is continuous on $[0,1]$ by [F4]. Each coordinate of $Q_{P_X}$ is linear in $P_X$, so the finite sum $H(Q_{P_X})$ is continuous on the input simplex. Therefore $P_X\mapsto I(P_X;W)$ is continuous.

The input simplex is nonempty because $\mathcal{X}$ is nonempty; it is closed and bounded in ${\mathbb{R}}^{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}$. By [F5], the continuous mutual-information function attains a maximum at some $P_X^{\ast }$. Its maximum equals the supremum in [F1], proving $I(P_X^{\ast };W)=C(W)$.

By [F1], $H(Y^n)={\sum }_{i=1}^{n}H(Y_i\mid Y^{i-1})$. For each $i$, [F2] gives $H(Y_i\mid Y^{i-1})\le H(Y_i)$, so $H(Y^n)\le {\sum }_{i}H(Y_i)$.

The conditional chain rule in [F1] gives $H(Y^n\mid X^n)={\sum }_{i}H(Y_i\mid X^n,Y^{i-1})$. For every positive-probability value $(x^n,y^{i-1})$, factorization [F3] and summing the unused future coordinates show that the conditional law of $Y_i$ is $W(\cdot \mid x_i)$. Thus $H(Y_i\mid X^n,Y^{i-1})=H(Y_i\mid X_i)$, including after averaging over conditioning values.

By [F1], $I(X^n;Y^n)=H(Y^n)-H(Y^n\mid X^n)$. Steps 1.1 and 1.2 therefore give $I(X^n;Y^n)\le {\sum }_{i=1}^n(H(Y_i)-H(Y_i\mid X_i))={\sum }_{i=1}^{n}I(X_i;Y_i)\le nC(W)$ by [F4].

On every pair with $P_X(x)W(y\mid x)>0$, the output marginal $Q_{P_X}(y)$ is positive. Thus [F1] gives a finite value, and summing its expectation gives $\mathbb{E}[{\mathrm{ı}}_{P_X}(X_1;Y_1)]={\sum }_{x,y:P_X(x)W(y\mid x)>0}{P}_X(x)W(y\mid x)\ln \frac{W(y\mid x)}{Q_{P_X}(y)}=I(P_X;W)$ by [F2]. The variable has finite support, hence some finite variance $v$. The row-law normalization is supplied by [F3].

Let $S_n:={\sum }_{i=1}^n{\mathrm{ı}}_{P_X}(X_i;Y_i)$. Independence gives $\mathbb{E}{S}_n=nI(P_X;W)$ and $\mathbb{E}[(S_n-\mathbb{E}{S}_n{)}^2]=nv$. For every $\eta >0$, the squared deviation is at least $n^2{\eta }^2$ on $\{\mathrm{\mid }{S}_n\mathrm{/}n-I(P_X;W)\mathrm{\mid }\ge \eta \}$, so that event has probability at most $v\mathrm{/}(n{\eta }^2)\to 0$. This is convergence in probability.

Fix $x\in \mathcal{X}$. Suppose some output reachable from $x$ has zero $Q^{\ast }$ mass, and put $a:={\sum }_{y:Q^{\ast }(y)=0}W(y\mid x)>0$. For $0<t<1$, let $P_t:=(1-t)P_X^{\ast }+t{\delta }_x$ and $Q_t:=P_{t}W=(1-t)Q^{\ast }+tW(\cdot \mid x)$. By [F2] and [F3], the conditional-entropy part of $I(P_t;W)-I(P_X^{\ast };W)$ is linear in $t$. On coordinates with $Q^{\ast }(y)>0$, differentiability in [F5] bounds the total entropy change in absolute value by $K_{1}t$ for some finite $K_1$ and all small $t$. For zero coordinates with $W(y\mid x)>0$, the entropy contribution is exactly $-tW(y\mid x)\ln t-tW(y\mid x)\ln W(y\mid x)$. All terms other than $-ta\ln t$ have absolute value at most $K_{2}t$ for a finite $K_2$. Since $-\ln t\to +\mathrm{\infty }$ by [F6], the information change is positive for sufficiently small $t$, contradicting maximality in [F1]. Every row therefore has support contained in $\mathrm{supp}{Q}^{\ast }$.

Now fix any $x$ and use the same segment $P_t=(1-t)P_X^{\ast }+t{\delta }_x$. By step 1.1, $Q^{\ast }$ is positive on the support of $W(\cdot \mid x)$, so the right derivative at $t=0$ is finite. Differentiating the entropy expression in [F2] with [F3] and [F5] gives ${\frac{d}{dt}I(P_t;W)\mid }_{0+}=-{\sum }_{y:Q^{\ast }(y)>0}(W(y\mid x)-Q^{\ast }(y))\ln Q^{\ast }(y)-H(W(\cdot \mid x))+{\sum }_u{P}_X^{\ast }(u)H(W(\cdot \mid u))=D(W(\cdot \mid x)\mathrm{\parallel }{Q}^{\ast })-C(W)$, where the $+1$ derivative terms cancel because both rows sum to one, and the last equality is [F2] and [F4].

Since $P_X^{\ast }$ maximizes information and $P_t$ is feasible for $t\ge 0$, the right derivative in step 2.1 is nonpositive. Hence $D(W(\cdot \mid x)\mathrm{\parallel }{Q}^{\ast })\le C(W)$. The input $x$ was arbitrary, proving the bound for all rows.

Let $S:=\{m:e_m\le 2{\epsilon }_{\mathrm{a}\mathrm{v}}\}$. If fewer than $M\mathrm{/}2$ messages belonged to $S$, then more than $M\mathrm{/}2$ messages would each have error greater than $2{\epsilon }_{\mathrm{a}\mathrm{v}}$, forcing ${\sum }_m{e}_m>M{\epsilon }_{\mathrm{a}\mathrm{v}}$, a contradiction. Hence $\mathrm{\mid }S\mathrm{\mid }\ge M\mathrm{/}2$.

Restrict the encoder to $S$ and relabel its messages. Define the new decoder to keep any old decoded message in $S$ and to output a fixed retained message otherwise. For each transmitted $m\in S$, every output previously decoded correctly as $m$ is still decoded correctly, so its new error is at most $e_m\le 2{\epsilon }_{\mathrm{a}\mathrm{v}}$. Thus the subcode has maximal error at most $2{\epsilon }_{\mathrm{a}\mathrm{v}}$; its rate loss is at most $n^{-1}\ln 2$ because $\mathrm{\mid }S\mathrm{\mid }\ge M\mathrm{/}2$.

If $R=0$, one message gives zero error. Otherwise choose $\delta :=(C(W)-R)\mathrm{/}3>0$ and $M_n:=\lfloor e^{nR}\rfloor$. Then $\ln M_n\mathrm{/}n\to R$, so for all sufficiently large $n$, $(\ln M_n+n\delta )\mathrm{/}n<C(W)-\delta$. By [F3], the probability that the transmitted IID pair fails the threshold ${\mathrm{ı}}_{P_X^{\ast }}(X^n;Y^n)>\ln M_n+n\delta$ tends to zero.

Draw $M_n$ codewords independently from $P_X^{\ast n}$. Decode to the unique codeword with information density greater than $\ln M_n+n\delta$, using a fixed default output if there is not exactly one. Conditional on the transmitted message, an error is contained in the union of the true-codeword miss event from step 1.1 and the event that some independent competing word passes the threshold. For one competitor $X^{\mathrm{\prime }n}\sim P_X^{\ast n}$ independent of $Y^n\sim Q_{P_X^{\ast }}^n$, [F2] gives $\mathbb{E}{e}^{{\mathrm{ı}}_{P_X^{\ast }}(X^{\mathrm{\prime }n};Y^n)}={\sum }_{x^n}{P}_X^{\ast n}(x^n){\sum }_{y^n:Q_{P_X^{\ast }}^n(y^n)>0}{W}^n(y^n\mid x^n)=1$ by [F4], since every output reachable from a positive-probability input has positive $Q_{P_X^{\ast }}$ mass. On a false pass, the nonnegative variable $Z=e^{{\mathrm{ı}}_{P_X^{\ast }}(X^{\mathrm{\prime }n};Y^n)}$ exceeds $e^{\ln M_n+n\delta }$, so $1=\mathbb{E}Z\ge e^{\ln M_n+n\delta }\mathrm{Pr}[Z>e^{\ln M_n+n\delta }]$, and the false-pass probability is at most $e^{-\ln M_n-n\delta }$. A union bound over at most $M_n-1$ competitors makes this term at most $e^{-n\delta }$.

The ensemble-averaged average error is at most the miss probability plus $e^{-n\delta }$, so it tends to zero by step 1.1 and step 2.1. The ensemble has finite support; therefore at each $n$ some deterministic codebook has average error no greater than the ensemble mean. Its rate tends to $R$, proving the claim.

For each $x\in \mathcal{X}$, the random variable $Z_x:=\ln (W(Y\mid x)\mathrm{/}{Q}^{\ast }(Y))$ under row law $W(\cdot \mid x)$ is finite on its support by [F1]. Its mean is $D(W(\cdot \mid x)\mathrm{\parallel }{Q}^{\ast })\le C(W)$, and it has finite variance because it takes only finitely many values. Thus $V:={\max }_{x\in \mathcal{X}}\mathrm{Var}(Z_x)$ is finite.

Fix $x^n$. By [F3], the coordinate log likelihoods are independent. Their sum $S_n$ therefore has mean at most $nC(W)$ and variance at most $nV$. On the event $S_n>n(C(W)+\delta )$ one has $\mathrm{\mid }{S}_n-\mathbb{E}{S}_n\mathrm{\mid }>n\delta$, so the squared deviation is at least $n^2{\delta }^2$. Taking expectations bounds the event probability by $\mathbb{E}[(S_n-\mathbb{E}{S}_n{)}^2]\mathrm{/}(n^2{\delta }^2)\le V\mathrm{/}(n{\delta }^2)$.

Since the encoder is deterministic and the channel law given $J=m$ depends on $m$ only through $X^n=e(m)$, $H(Y^n\mid J)=H(Y^n\mid X^n)$. By [F2], $I(J;Y^n)=I(X^n;Y^n)$.

By [F1] and [F2], $\ln M=I(J;Y^n)+H(J\mid Y^n)\le I(X^n;Y^n)+\ln 2+{\epsilon }_{\mathrm{a}\mathrm{v}}\ln M\le nC(W)+\ln 2+{\epsilon }_{\mathrm{a}\mathrm{v}}\ln M$ using [F4].

For a reliable code sequence, rearrange step 2.1 to get $(1-{\epsilon }_{\mathrm{a}\mathrm{v}}(n))n^{-1}\ln M_n\le C(W)+n^{-1}\ln 2$. The left coefficient tends to one and the right side tends to $C(W)$, so $\mathrm{lim\hspace{0.17em}sup}{n}^{-1}\ln M_n\le C(W)$.

By [F1] choose a maximizing input law $P_X^{\ast }$ and set $Q^{\ast }:=P_X^{\ast }W$. Fix a blocklength $n$, a codeword $x_m^n=e(m)$, and a threshold $\tau$. Split $D_m$ within the support of $W^n(\cdot \mid x_m^n)$ into outputs where $\ln (W^n(y^n\mid x_m^n)\mathrm{/}(Q^{\ast }{)}^n(y^n))>\tau$ and the supported complement. The first part has channel probability at most the threshold-tail probability in [F2]. On the supported complement, $W^n(y^n\mid x_m^n)\le e^{\tau }(Q^{\ast }{)}^n(y^n)$ by the likelihood ratio; outside the support, $W^n(y^n\mid x_m^n)=0$, so the same inequality holds there. Hence the remaining channel probability is at most $e^{\tau }(Q^{\ast }{)}^n(D_m)$.

Average the bound in step 1.1 over messages. The tail term is at most $V\mathrm{/}(n{\eta }^2)$ uniformly by [F2]. Pairwise disjointness from [F3] gives ${\sum }_m(Q^{\ast }{)}^n(D_m)\le 1$, so average success is at most $V\mathrm{/}(n{\eta }^2)+e^{\tau }\mathrm{/}{M}_n$.

Choose $\eta >0$ such that eventually $n^{-1}\ln M_n\ge C(W)+2\eta$, which is possible by the strict liminf hypothesis. Set $\tau =n(C(W)+\eta )$. Then $e^{\tau }\mathrm{/}{M}_n\le e^{-n\eta }$, and step 2.1 bounds success by $V\mathrm{/}(n{\eta }^2)+e^{-n\eta }\to 0$. Thus average error tends to one. Since maximal error is at least average error, it too tends to one.

A maximal-error reliable sequence is also average-error reliable because ${\epsilon }_{\mathrm{a}\mathrm{v}}\le {\epsilon }_{\max }$. Thus [F3] gives $C_{\max }(W)\le C_{\mathrm{a}\mathrm{v}}(W)\le C(W)$.

By [F4], every $0\le R<C(W)$ is average-error achievable, so $C_{\mathrm{a}\mathrm{v}}(W)\ge C(W)$ after taking the supremum when $C(W)>0$. If $C(W)=0$, [F7] gives $C_{\mathrm{a}\mathrm{v}}(W)\ge 0$. The case split is exhaustive by [F6]; in either case $C_{\mathrm{a}\mathrm{v}}(W)=C(W)$.

If $C(W)>0$, fix any $0\le R<C(W)$. By [F4] there is an average-error reliable sequence at rate at least $R$. Apply [F5] to each code: the maximal errors tend to zero and the log message count loses at most $\ln 2$ at blocklength $n$, so the resulting rate is still at least $R$ in the limit. Thus $C_{\max }(W)\ge R$ for every such $R$, and hence $C_{\max }(W)\ge C(W)$. If $C(W)=0$, [F7] gives $C_{\max }(W)\ge 0=C(W)$. The cases are exhaustive by [F6], and step 1.1 gives equality.