A channel is a Markov kernel. Its capacity is a variational quantity: the largest mutual information induced by an input distribution.
Discrete memoryless channel
Definition. A discrete memoryless channel is a stochastic matrix \(W(y\mid x)\). For input law \(P_X\), it induces \(P_XW\) on outputs and mutual information \[ I(P_X,W)=\sum_{x,y}P_X(x)W(y\mid x)\log\frac{W(y\mid x)}{(P_XW)(y)}. \]
Capacity
Definition. The channel capacity is \[ C=\max_{P_X} I(P_X,W). \] The maximum exists for finite alphabets because the simplex is compact and \(I(P_X,W)\) is continuous.
Concavity in the input law
Proposition. For fixed \(W\), the map \(P_X\mapsto I(P_X,W)\) is concave. For fixed \(P_X\), mutual information is convex in the channel law.
Proof by entropy form
Proof. Write \(I(X;Y)=H(Y)-H(Y\mid X)\). As \(P_X\) varies, \(H(Y)\) is concave in \(P_X\), while \(H(Y\mid X)=\sum_xP_X(x)H(W(\cdot\mid x))\) is linear. This proves concavity.
Discrete memoryless channels
Definition. A channel is a stochastic kernel \(W(y\mid x)\) from input alphabet \(\mathcal X\) to output alphabet \(\mathcal Y\). A discrete memoryless channel acts on blocks by \[ W^n(y^n\mid x^n)=\prod_{i=1}^nW(y_i\mid x_i). \]
Definition. Its capacity is \[ C=\max_{P_X}I(X;Y), \] where \(P_{XY}=P_XW\).
Concavity in the input law
Theorem. For fixed channel \(W\), \(I(P_X,W)\) is concave in \(P_X\).
Proof. \[ I(X;Y)=H(P_XW)-\sum_xP_X(x)H\{W(\cdot\mid x)\}. \] The first term is entropy of a linear image of \(P_X\), hence concave; the second is linear. On a finite simplex, continuity ensures a maximizer exists.
Binary symmetric channel
Theorem. The binary symmetric channel \(Y=X\oplus Z\), \(Z\sim\operatorname{Bernoulli}(\varepsilon)\), has capacity \[ C=\log2-h_2(\varepsilon) \] nats per use, achieved by uniform input.
Proof. \(H(Y\mid X)=h_2(\varepsilon)\), independent of input. Thus \[ I(X;Y)=H(Y)-h_2(\varepsilon)\le\log2-h_2(\varepsilon). \] Uniform \(X\) makes \(Y\) uniform and attains equality.
Binary erasure channel
Theorem. A binary erasure channel with erasure probability \(\delta\) has capacity \[ C=(1-\delta)\log2. \]
Proof. Let \(E\) indicate erasure. Since \(E\) is independent of \(X\), \[ I(X;Y,E)=I(X;E)+I(X;Y\mid E) =(1-\delta)H(X). \] The erasure indicator is determined by \(Y\), so this equals \(I(X;Y)\). Maximize at uniform \(X\).
Weakly symmetric channels
Theorem. If every row of the channel matrix is a permutation of every other row and all column sums agree, then uniform input achieves capacity \[ C=\log|\mathcal Y|-H(W(\cdot\mid x)), \] where row entropy is independent of \(x\).
Proof. Conditional output entropy is the common row entropy for every input law. Uniform input and equal column sums make output uniform, maximizing \(H(Y)\). No other input can exceed \(\log|\mathcal Y|\).
Information-radius characterization
Theorem. \[ C=\min_{Q_Y}\max_xD\{W(\cdot\mid x)\|Q_Y\}. \]
Proof outline. For every input \(P_X\) and output reference \(Q_Y\), \[ \sum_xP_X(x)D(W_x\|Q_Y) =I(X;Y)+D(P_Y\|Q_Y). \] Therefore \(I(X;Y)\le\max_xD(W_x\|Q_Y)\). Minimize in \(Q_Y\). Convex minimax gives equality; at a capacity-achieving input, the induced output is an information center.
KKT conditions for capacity
Theorem. An input law \(P_X^*\) with induced output \(P_Y^*\) is capacity-achieving if and only if \[ D(W_x\|P_Y^*)\le C \quad\text{for every }x, \] with equality for every \(x\) in the support of \(P_X^*\).
Proof outline. The directional derivative of \(I(P_X,W)\) toward point mass at \(x\) is \(D(W_x\|P_Y)-I(P_X,W)\). Concave maximization requires every feasible directional derivative to be nonpositive and complementary slackness gives equality on positive-mass inputs.
Cost-constrained capacity
Definition. With input cost \(c(x)\) and budget \(\Gamma\), \[ C(\Gamma)= \max_{P_X:\mathbb Ec(X)\le\Gamma}I(X;Y). \]
\(C(\Gamma)\) is nondecreasing and concave in \(\Gamma\). A Lagrange multiplier prices cost, and active inputs satisfy a modified divergence equality \[ D(W_x\|P_Y^*)-\lambda c(x)=\text{constant}. \]
Feedback and memorylessness
Perfect causal feedback does not increase capacity of a discrete memoryless channel, although it can improve reliability and simplify coding. For channels with memory, feedback capacity is expressed through directed information and can increase.