Past exam of the communication Theory course of the University of Oxford / 2009 / 3

For finite-valued variables, mutual information isTerms of zero joint probability are zero. A discrete memoryless channel has fixed transition probabilities $W(y\mid x)$ on finite alphabets, and conditional on an input sequence its outputs are independent with the product law ${\prod }_{i}W(y_i\mid x_i)$. Its channel capacity isbits per channel use. The maximum is over all input distributions, with the transition law held fixed.

Let the probability of the first input be $t$. The two equal output probabilities are $(2+t)/6$, and the third is $s=(1-t)/3$. Writing $h_2$ for the binary entropy function, the output entropy is $h_2(s)+(1-s)$, while the conditional entropy is $t+(1-t){\log }_{2}3$. ThereforeThe derivative with respect to $s$ isand the second derivative is $-1/(\ln 2s(1-s))<0$ in the interior. Thus the unique stationary point is the global maximum. It occurs at $s=4/31$, soThe capacity itself is $\boxed{C={\log }_2(31/27)}$. The maximization is over $t$, not over arbitrary output distributions; $s=(1-t)/3$ keeps the feasible outputs explicit.

Let $E$ record whether the second stage erased the symbol, and write its output as $Z$. The erasure marker is outside the original output alphabet, so $E$ is determined by $Z$. Independence makes $E$ independent of both $X$ and the first output $Y$. The chain rule for mutual information therefore givesThe erased branch gives zero information because its output is constant; the unerased branch has exactly the original joint input-output law. Maximizing over the same input distributions givesThis includes $p=0$ and $p=1$. It is the capacity after independent output erasure; input-dependent erasure would not justify the independence step.