Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 1 / 12G / Solution

For a binary symmetric channel with crossover probability $p$, Shannon's noisy coding theorem gives capacity $C=1-h_2(p)$ bits per use, where $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. For any rate below capacity there are block codes with block length tending to infinity and decoding error tending to zero. Conversely, vanishing-error transmission cannot have asymptotic rate above capacity. At $p=1/2$ the capacity is zero; the formula also covers $p>1/2$ by complementing the output.

For discrete random variables, mutual information isThe formula is symmetric. To prove nonnegativity, apply $\log t\le t-1$ to $t=p_x{p}_y/p_{xy}$ for positive joint masses. Multiplication by $p_{xy}$ and summation gives $-I\log 2\le {\sum }_{p_{xy}>0}{p}_x{p}_y-1\le 0$. Hence $I\ge 0$, with equality precisely for independence. The channel information capacity is ${\sup }_{p_X}I(X;Y)$, over input distributions.

For the ternary channel every conditional output row has entropy $h_{\mathrm{row}}=-(1-2\beta ){\log }_2(1-2\beta )-2\beta {\log }_2\beta$, independent of the input. Therefore $I=H(Y)-h_{\mathrm{row}}\le {\log }_{2}3-h_{\mathrm{row}}$. Uniform input produces uniform output, since the matrix is doubly stochastic, and attains the bound. ThusUse $0\log 0=0$ at the endpoints. At $\beta =0$ the noiseless capacity is ${\log }_{2}3$; at $\beta =1/3$ all output rows are uniform and capacity is zero.