Past exam of the information theory course of the University of Oxford / 2021 / 3 / c

Interpret additive noise in the standard channel sense: $Z$ is independent of the chosen input $X$ and its law is fixed as the input law is varied. A uniform marginal law for $Z$ alone, without this independence assumption, would not specify the transition matrix. Only reachable output symbols are counted.

Translate the output alphabet by $-\min (z_1,z_2)$ and put $d=|z_2-z_1|\ge 1$. The reachable outputs becomeFor $d=1$ the two sets overlap in two points; for $d=2$ in one; for $d\ge 3$ they are disjoint. In particular $|\mathcal{Y}|\ge 4$, and choosing noise values $0,1$ attains four.

With rows indexed by inputs $0,1,2$ and columns by outputs $0,1,2,3$, independence and uniform two-point noise giveEvery conditional output distribution has information entropy one bit, so $I(X;Y)=H(Y)-1\le {\log }_{2}4-1=1$. The input probability mass function $(1/2,0,1/2)$ makes all four outputs equiprobable, attaining that bound. ThusUsing a zero-probability input in a channel-capacity maximization is legitimate; it is unrelated to the strictly positive source weights needed for the tree-shape claims in Question 2.

Each of the three input values has two possible outputs, so their union has at most six elements. The preceding union formula also gives this bound. Choose noise values $0,3$, whose two translated input alphabets are disjoint. With columns ordered $0,1,2,3,4,5$ the transition matrix isThus $|\mathcal{Y}|=6$. Every output determines its input, explicitly $X=Y\mathrm{mod}3$, so $H(X\mid Y)=0$. Consequently $I(X;Y)=H(X)\le {\log }_{2}3$, with equality for a uniform input. ThereforeThe extra uncertainty of which noise value occurred does not reduce information about the input: the two possible outputs for each input remain distinguishable from those of every other input.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn 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 $C\ge 1$ 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\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-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 considerThe 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 yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis 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.