Channel Capacity

Step 1: The rows being permutations kills the noise term’s dependence on $p(x)$. Letting $r$ denote a row of the transition matrix, every row has the same entropy $H(r)$, so

$I(X;Y) = H(Y) - H(Y \mid X) = H(Y) - H(r)$

Step 2: Bound the remaining term. By the maximum entropy bound,

$I(X;Y) \le \log \lvert \mathcal{Y} \rvert - H(r)$

with equality iff the output distribution is uniform.

Step 3: The equal column sums make the uniform input produce a uniform output. Take $p(x) = 1/\lvert \mathcal{X} \rvert$. Then

$p(y) = \sum_{x \in \mathcal{X}} p(y \mid x) p(x) = \frac{1}{\lvert \mathcal{X} \rvert} \sum_x p(y \mid x) = \frac{c}{\lvert \mathcal{X} \rvert} = \frac{1}{\lvert \mathcal{Y} \rvert}$

where $c$ is the (common) column sum. So the bound in Step 2 is attained.

∎

Step 1: Each marginal concentrates. By the weak law of large numbers, $-\frac{1}{n} \log p(X^n) \rightarrow -\mathbb{E}[\log p(X)] = H(X)$ in probability. So given $\epsilon > 0$ there exists $n_1$ such that for all $n > n_1$,

$\Pr\left\{ \left\lvert -\tfrac{1}{n} \log p(X^n) - H(X) \right\rvert \ge \epsilon \right\} < \frac{\epsilon}{3}$

Step 2: Repeat for $Y$ and for the pair. Identically, $-\frac{1}{n}\log p(Y^n) \rightarrow H(Y)$ and $-\frac{1}{n}\log p(X^n, Y^n) \rightarrow H(X,Y)$ in probability, giving $n_2$ and $n_3$ with each failure probability below $\epsilon/3$.

Step 3: Union bound. Choosing $n > \max\{n_1, n_2, n_3\}$, the probability of the union of the three bad events is less than $3 \cdot \epsilon/3 = \epsilon$. Hence $\Pr(A_\epsilon^{(n)}) > 1 - \epsilon$. This is why each budget was set to $\epsilon/3$ — so the three failures sum to exactly $\epsilon$.

∎

Identical in shape to the size bound in the single-variable AEP:

$1 = \sum_{x^n, y^n} p(x^n, y^n) \ge \sum_{A_\epsilon^{(n)}} p(x^n, y^n) \ge \big\lvert A_\epsilon^{(n)} \big\rvert\, 2^{-n(H(X,Y) + \epsilon)}$

since each jointly typical pair has probability at least $2^{-n(H(X,Y)+\epsilon)}$. Rearranging gives $\lvert A_\epsilon^{(n)} \rvert \le 2^{n(H(X,Y) + \epsilon)}$.

∎

Upper bound. If $\tilde{X}^n$ and $\tilde{Y}^n$ are independent with the same marginals, then

$\Pr\big((\tilde{X}^n, \tilde{Y}^n) \in A_\epsilon^{(n)}\big) = \sum_{(x^n, y^n) \in A_\epsilon^{(n)}} p(x^n) p(y^n)$

There are at most $2^{n(H(X,Y) + \epsilon)}$ terms (part 2), and each term is at most $2^{-n(H(X) - \epsilon)} \cdot 2^{-n(H(Y) - \epsilon)}$ by joint typicality:

$\le 2^{n(H(X,Y) + \epsilon)}\, 2^{-n(H(X) - \epsilon)}\, 2^{-n(H(Y) - \epsilon)} = 2^{-n(I(X;Y) - 3\epsilon)}$

using $I(X;Y) = H(X) + H(Y) - H(X,Y)$ and collecting the three $\epsilon$‘s — which is where the $3\epsilon$ comes from.

Lower bound. For $n$ large, $\Pr(A_\epsilon^{(n)}) \ge 1 - \epsilon$, so

$1 - \epsilon \le \sum_{A_\epsilon^{(n)}} p(x^n, y^n) \le \big\lvert A_\epsilon^{(n)} \big\rvert\, 2^{-n(H(X,Y) - \epsilon)}$

giving $\lvert A_\epsilon^{(n)} \rvert \ge (1-\epsilon) 2^{n(H(X,Y) - \epsilon)}$. Feeding this count through the same product bound in the other direction:

$\Pr\big((\tilde{X}^n, \tilde{Y}^n) \in A_\epsilon^{(n)}\big) \ge (1-\epsilon) 2^{n(H(X,Y) - \epsilon)} 2^{-n(H(X) + \epsilon)} 2^{-n(H(Y) + \epsilon)} = (1-\epsilon) 2^{-n(I(X;Y) + 3\epsilon)}$

∎

Setup: generate a random codebook. Fix $p(x)$. Generate $2^{nR}$ codewords independently according to $p(x^n) = \prod_{i=1}^n p(x_i)$, and display them as the rows of a matrix

$\mathcal{C} = \begin{bmatrix} x_1(1) & \cdots & x_n(1) \\ \vdots & & \vdots \\ x_1(2^{nR}) & \cdots & x_n(2^{nR}) \end{bmatrix}$

Every entry is i.i.d. $\sim p(x)$, so $\Pr(\mathcal{C}) = \prod_{w=1}^{2^{nR}} \prod_{i=1}^n p(x_i(w))$.

The protocol.

1. A random code $\mathcal{C}$ is generated as above.
2. $\mathcal{C}$ is revealed to both sender and receiver, who also know $p(y \mid x)$.
3. A message $W$ is chosen uniformly: $\Pr(W = w) = 2^{-nR}$.
4. The $w$th codeword $X^n(w)$ is sent.
5. The receiver receives $Y^n \sim \prod_i p(y_i \mid x_i(w))$.
6. The receiver declares $\hat{W}$ if $(X^n(\hat{W}), Y^n)$ is jointly typical and there is no other index $W' \ne \hat{W}$ with $(X^n(W'), Y^n) \in A_\epsilon^{(n)}$. If no such $\hat{W}$ exists, or more than one does, an error is declared.
7. Error event $\mathcal{E} = \{\hat{W} \ne W\}$.

Step 1: Average over codebooks, and exploit symmetry. Rather than analyze one code, compute

$\Pr(\mathcal{E}) = \sum_\mathcal{C} \Pr(\mathcal{C}) P_e^{(n)}(\mathcal{C}) = \frac{1}{2^{nR}}\sum_{w=1}^{2^{nR}} \sum_\mathcal{C} \Pr(\mathcal{C}) \lambda_w(\mathcal{C})$

By the symmetry of the code construction, $\sum_\mathcal{C} \Pr(\mathcal{C})\lambda_w(\mathcal{C})$ does not depend on $w$ — every codeword was generated the same way. So we may assume without loss of generality that $W = 1$ was sent:

$\Pr(\mathcal{E}) = \Pr(\mathcal{E} \mid W = 1)$

This is the single biggest simplification in the proof, and it is bought entirely by randomizing the codebook.

Step 2: Name the two ways to fail. Define $E_i = \{(X^n(i), Y^n) \in A_\epsilon^{(n)}\}$ for $i \in \{1, \ldots, 2^{nR}\}$. With $W = 1$ sent, an error occurs if either:

• $E_1^c$ — the true codeword is not jointly typical with the output, or
• $E_2 \cup E_3 \cup \cdots \cup E_{2^{nR}}$ — some wrong codeword is.

By the union bound,

$\Pr(\mathcal{E} \mid W=1) \le P(E_1^c \mid W=1) + \sum_{i=2}^{2^{nR}} P(E_i \mid W=1)$

Step 3: Bound the first source of error. By joint AEP part 1, $P(E_1^c \mid W = 1) \rightarrow 0$, so $P(E_1^c \mid W=1) \le \epsilon$ for $n$ sufficiently large.

Step 4: Bound each rival. By the code generation process, $X^n(1)$ and $X^n(i)$ are independent for $i \ne 1$; hence so are $Y^n$ and $X^n(i)$ (since $Y^n$ depends only on $X^n(1)$). So joint AEP part 3 applies exactly: $P(E_i \mid W = 1) \le 2^{-n(I(X;Y) - 3\epsilon)}$.

Step 5: Assemble.

$\Pr(\mathcal{E}) \le \epsilon + \sum_{i=2}^{2^{nR}} 2^{-n(I(X;Y) - 3\epsilon)} = \epsilon + \big(2^{nR} - 1\big) 2^{-n(I(X;Y) - 3\epsilon)}$

$\le \epsilon + 2^{3n\epsilon}\, 2^{-n(I(X;Y) - R)} \;\le\; 2\epsilon$

if $n$ is sufficiently large and $R < I(X;Y) - 3\epsilon$. Read the exponent: the number of rivals grows like $2^{nR}$ and each is fooled with probability $2^{-nI}$, so the product vanishes precisely when $R < I$.

Step 6: Three surgeries to upgrade the conclusion.

1. Optimize the input distribution. Choose $p(x) = p^*(x)$, the distribution achieving capacity. Then the condition $R < I(X;Y)$ becomes $R < C$.
2. Remove the average over codebooks. Since the average error over codebooks is $\le 2\epsilon$, at least one codebook $\mathcal{C}^*$ has $\Pr(\mathcal{E} \mid \mathcal{C}^*) \le 2\epsilon$. (An exhaustive search over all $(2^{nR}, n)$ codes would find it.) This is the classic probabilistic-existence move: we never construct a good code, we prove the average is good and conclude one must be.
3. Convert average error into maximal error. The arithmetic average $\frac{1}{2^{nR}}\sum_i \lambda_i(\mathcal{C}^*) \le 2\epsilon$ implies at least half the indices have $\lambda_i < 4\epsilon$ — otherwise that half alone would contribute more than $2\epsilon$ to the average. Throw away the worst half of the codewords. The survivors have maximal probability of error below $4\epsilon$, and we are left with $2^{nR - 1}$ codewords, i.e. rate $R' = R - \frac{1}{n}$ — negligible for large $n$.

Combining: a code of rate $R - \frac{1}{n}$ with $\lambda^{(n)} \le 4\epsilon$, proving achievability of any rate below capacity.

∎

Assume a $(2^{nR}, n)$ code with zero probability of error, so the decoder output $g(Y^n)$ equals $W$ with probability 1 — meaning $W$ is determined by $Y^n$, i.e. $H(W \mid Y^n) = 0$. Assume $W$ uniform, so $H(W) = nR$. Then

$nR = H(W) = \underbrace{H(W \mid Y^n)}_{= 0} + I(W; Y^n) = I(W; Y^n)$

$\overset{(a)}{\le} I(X^n; Y^n) \overset{(b)}{\le} \sum_{i=1}^n I(X_i; Y_i) \overset{(c)}{\le} nC$

where (a) is the data processing inequality applied to the Markov chain $W \rightarrow X^n(W) \rightarrow Y^n$, (b) is proved below as the single-letterization lemma using the memorylessness of the channel, and (c) is the definition of information capacity. Hence for any zero-error code and all $n$: $R \le C$.

∎

Since $W$ is uniform, $P_e^{(n)} = \Pr(W \ne \hat{W})$. Apply the general form $H(P_e) + P_e \log \lvert \mathcal{W} \rvert \ge H(W \mid \hat{W})$ with $\lvert \mathcal{W} \rvert = 2^{nR}$, and weaken $H(P_e) \le 1$.

∎

Step 1: Expand and use memorylessness.

$I(X^n; Y^n) = H(Y^n) - H(Y^n \mid X^n) = H(Y^n) - \sum_{i=1}^n H(Y_i \mid Y_1, \ldots, Y_{i-1}, X^n)$

$= H(Y^n) - \sum_{i=1}^n H(Y_i \mid X_i)$

since by the definition of a DMC, $Y_i$ depends only on $X_i$ and is conditionally independent of everything else. This is the step that would fail with feedback.

Step 2: Subadditivity of joint entropy. By the independence bound, $H(Y^n) \le \sum_i H(Y_i)$:

$I(X^n; Y^n) \le \sum_{i=1}^n H(Y_i) - \sum_{i=1}^n H(Y_i \mid X_i) = \sum_{i=1}^n I(X_i; Y_i)$

Step 3: Definition of capacity. Each term is at most $C$, so $I(X^n; Y^n) \le nC$.

∎

If $\lambda^{(n)} \rightarrow 0$ then $P_e^{(n)} \rightarrow 0$. Fix the encoding and decoding rules, so $W \rightarrow X^n(W) \rightarrow Y^n \rightarrow \hat{W}$, with $W$ uniform. Then

$nR \overset{(a)}{=} H(W) \overset{(b)}{=} H(W \mid \hat{W}) + I(W; \hat{W})$ $\overset{(c)}{\le} 1 + P_e^{(n)} nR + I(W; \hat{W})$ $\overset{(d)}{\le} 1 + P_e^{(n)} nR + I(X^n; Y^n)$ $\overset{(e)}{\le} 1 + P_e^{(n)} nR + nC$

where (a) is uniformity of $W$, (b) is an identity, (c) is Fano’s inequality for $W$ taking at most $2^{nR}$ values, (d) is the data processing inequality, and (e) is the lemma above.

Divide by $n$:

$R \le P_e^{(n)} R + \frac{1}{n} + C$

Letting $n \rightarrow \infty$, the first two terms on the right vanish, so $R \le C$.

∎