Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 11K / c / Solution

Shannon second coding theorem states that the operational capacity of a discrete memoryless channel equalsevery rate below $C$ is achievable with error probability tending to zero, while rates above $C$ are not.

Put $d=b-a$. If $d=0$, then $Y=X+a$, so $X$ is recovered exactly and $C=1$ bit. If $|d|\ge 2$, the two output supportsare disjoint, so again $Y$ determines $X$ and $C=1$.

If $|d|=1$, one output value is common to both inputs and occurs with probability $1/2$ independently of the input, while either of the other two values reveals the input. The channel is therefore a binary erasure channel with erasure probability $1/2$, whose capacity is $1/2$ bit. Hence

Solved by gpt-5.6-sol high.