= Solution
Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The <transition matrix>, in that column order, is
$$
M=\begin{pmatrix}
1/2&0&1/2&0&0\\
0&1/2&0&1/2&0\\
0&0&1/2&0&1/2
\end{pmatrix}.
$$
An input <probability mass function> $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence \b[$C\geq1$ <bit> per use], as required for comparison with the four-output case.
There is a strict improvement, which can also be computed exactly. <Reflection> of the input labels $0\leftrightarrow2$, accompanied by output <reflection> $y\leftrightarrow4-y$, leaves <mutual information> unchanged. <Concavity of information entropy> makes <mutual information> a concave function of the input <probability mass function> for a fixed <transition matrix>. Averaging an input law with its <reflection> therefore cannot decrease it. It suffices to consider
$$
p_X=(s/2,1-s,s/2),\qquad 0\leq s\leq1.
$$
The outputs whose labels are <even integers> have total mass $s$ and <conditional probability mass function> $(1/4,1/2,1/4)$, with <information entropy> $3/2$. The outputs whose labels are <odd integers> have mass $1-s$ and <conditional probability mass function> $(1/2,1/2)$, with <information entropy> one. Splitting first by output <parity> using the <chain rule for information entropy> yields
$$
H(Y)=h_2(s)+\tfrac32s+(1-s),\qquad I(X;Y)=h_2(s)+\frac s2.
$$
Its <derivative> is $\log_2((1-s)/s)+1/2$, and its <second derivative> is negative. The unique maximum occurs at $s=\sqrt2/(1+\sqrt2)$, giving
$$
\boxed{C=\log_2(1+\sqrt2)\approx1.271553,\qquad p_X=\left(\frac1{2+\sqrt2},\frac1{1+\sqrt2},\frac1{2+\sqrt2}\right).}
$$
This additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.
\Image[/past-exam-of-the-information-theory-course-of-the-university-of-oxford/2021-two-point-noise-channels.png]
{title=Three original additive-noise channel diagrams: increasing noise separation changes output collisions and channel capacity}
Back to article page
