Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 2 / 11G / Solution

For a discrete memoryless channel, its channel capacity in bits per use is $C={\max }_{P_X}I(X;Y)$. The Shannon second coding theorem identifies this with the supremum of rates achievable by arbitrarily long block codes with error probability tending to zero: every rate below $C$ is achievable, and no rate above $C$ can have vanishing error. The channel is used independently at each transmission, and coding rate is measured using base-two logarithms.

Let $q$ be the probability of using the second input symbol. The second output symbol occurs with probability $q/2$, so $H(Y)=h_2(q/2)$. The first input has deterministic output and the second has one bit of conditional output Shannon entropy; hence $H(Y\mid X)=q$ andFor $0<q<1$, its derivative is $\frac{1}{2}{\log }_2[(2-q)/q]-1$, which vanishes at $q=2/5$. Strict concavity of binary entropy makes this the unique global maximum. Substituting givesThus Shannon's theorem supplies operational coding rates arbitrarily close to this value from below, and rules out reliable transmission above it.