The Exercise

A sender puts one bit $x \in \{0,1\}$ into a noisy line, and a receiver reads what comes out. In the binary symmetric channel the bit arrives flipped with probability $p$ and intact otherwise, and the receiver cannot tell a flipped bit from an intact one. In the erasure channel the bit is lost with probability $p$ and arrives intact otherwise; a lost bit arrives as a blank symbol $e$, so the receiver knows which bits are missing and learns nothing about their values. The exercise asks for the capacity of the erasure channel and how it compares with that of the binary symmetric channel at the same $p$.

The library answers with the capacity of the erasure channel in closed form and two inequalities between the capacities of the two channels.

Two Channels

A channel $q$ with finite input and output alphabets is given by its transition probabilities $q(y|x)$, the probability that the input $x$ leaves the channel as the output $y$.

The binary symmetric channel $B_p$ with flip probability $p$ has input and output alphabet $\{0,1\}$ and transition probabilities $$B_p(y|x) = \begin{cases} 1-p, & y = x,\\ p, & y \neq x. \end{cases}$$(1)^✦

The erasure channel $E_p$ with erasure probability $p$ has input alphabet $\{0,1\}$, output alphabet $\{0,1,e\}$ and transition probabilities $$E_p(y|x) = \begin{cases} p, & y = e,\\ 1-p, & y = x,\\ 0, & y \in \{0,1\},\ y \neq x. \end{cases}$$(2)^✦

Capacity

The Shannon entropy $H(P)$ of a distribution $P$ on a finite set, measured in nats, is $$H(P) = -\sum_i P(i) \log P(i),$$(3)^✦ with the natural logarithm and $0 \log 0 = 0$.

The marginals $P_X$ and $P_Y$ of a joint distribution $P$ of $X$ and $Y$ on finite sets are the distributions of $X$ alone and of $Y$ alone: $$P_X(x) = \sum_y P(x,y), \qquad P_Y(y) = \sum_x P(x,y).$$(4)

The mutual information $H(X:Y)$ of a joint distribution $P$ of $X$ and $Y$ is the number built from the entropy (3) of $P$ and of its marginals (4), $$H(X:Y) = H(P_X) + H(P_Y) - H(P).$$(5)^✦

The joint distribution $P_{XY}$ of a channel $q$ with input distribution $\lambda$ is the distribution of input and output when the inputs are drawn from $\lambda$: $$P_{XY}(x,y) = \lambda(x)\, q(y|x).$$(6)^✦

The mutual information $H_\lambda(X:Y)$ of a channel $q$ at the input distribution $\lambda$ is the mutual information (5) of its joint distribution (6).^✦

The capacity $C(q)$ of a channel $q$ is the supremum of this quantity over all probability distributions $\lambda$ on its inputs: $$C(q) = \sup_{\lambda} H_\lambda(X:Y).$$(7)^✦

The Claim

In bits, the capacity (8) is $1-p$ per use of the channel.

What Is Checked

The three statements are stated over the capacity (7) of the binary symmetric channel (1) and of the erasure channel (2).

About these two channels the library proves the closed form (8) and the two comparisons (9) and (10).