The Exercise

A message is sent through two noisy classical channels in a row: whatever comes out of the first is fed into the second. Show that the capacity of the chain is at most the smaller of the two capacities^✦, and that it can be strictly smaller: a binary symmetric channel with crossover probability $p$, $0 < p < \tfrac12$, followed by a second copy of itself gives a chain whose capacity lies below that of a single copy.^✦

Classical Channels

A discrete memoryless channel $N$ from a finite input alphabet $\mathcal{X}$ to a finite output alphabet $\mathcal{Y}$ is a family of conditional probabilities $N(y|x)$, the probability of receiving the letter $y$ when $x$ is sent, nonnegative and normalized for each input: $$N(y|x) \ge 0, \qquad \sum_{y \in \mathcal{Y}} N(y|x) = 1 \quad \text{for every } x \in \mathcal{X}.$$(1)^✦

The binary symmetric channel $N_p$ with crossover probability $p$ is the channel on the bit alphabet $\{0,1\}$ that returns the bit sent with probability $1-p$ and flips it with probability $p$: $$N_p(y|x) = \begin{cases} 1-p, & y = x, \\ p, & y \neq x. \end{cases}$$(2)^✦

The composite $N_2 \circ N_1$ of a channel $N_1$ from $\mathcal{X}$ to $\mathcal{Y}$ and a channel $N_2$ from $\mathcal{Y}$ to $\mathcal{Z}$ is the channel from $\mathcal{X}$ to $\mathcal{Z}$ that passes the input through $N_1$ and then the output of $N_1$ through $N_2$: $$(N_2 \circ N_1)(z|x) = \sum_{y \in \mathcal{Y}} N_1(y|x)\, N_2(z|y).$$(3)^✦

Entropy and Capacity

The Shannon entropy $H(r)$ of a probability distribution $r$ on a finite set $\mathcal{A}$ is $$H(r) = -\sum_{a \in \mathcal{A}} r(a) \log r(a),$$(4)^✦ with the natural logarithm, so that entropies are measured in nats.

Let $p_{XY}$ be a joint distribution of random variables $X$ and $Y$ on $\mathcal{X} \times \mathcal{Y}$. Its marginals $p_X$ and $p_Y$ are the distributions of $X$ alone and of $Y$ alone, $p_X(x) = \sum_y p_{XY}(x,y)$^✦ and $p_Y(y) = \sum_x p_{XY}(x,y)$^✦.

The mutual information $H(X:Y)$ of $p_{XY}$ is the sum of the entropies of the two marginals minus the joint entropy: $$H(X:Y) = H(p_X) + H(p_Y) - H(p_{XY}).$$(5)^✦

A channel $N$ from $\mathcal{X}$ to $\mathcal{Y}$, fed with an input distribution $q$ on $\mathcal{X}$, gives its input $X$ and output $Y$ the joint distribution $$p_{XY}(x,y) = q(x)\, N(y|x),$$(6)^✦ and the mutual information of $N$ at $q$ is $H(X:Y)$ computed from this joint distribution.^✦

The capacity $C(N)$ of $N$ is the supremum, over all input distributions $q$ on $\mathcal{X}$, of the mutual information $H(X:Y)$ of $N$ at $q$: $$C(N) = \sup_{q} H(X:Y).$$(7)^✦

The Claim

What Is Checked

Both theorems are stated over the capacity (7), built from the mutual information (5), and over the composite channel (3); the first takes any two discrete memoryless channels (1), the second the binary symmetric channel (2) twice over.