Past exam of the communication Theory course of the University of Oxford / 2010 / 3 / c

Let the input probabilities be $(s,t,u)$ and put $v=s+u=1-t$. The output distribution and conditional entropy areFor fixed $v$, the first and third output masses sum to $v/2$. Their entropy is maximized when they are equal, so $s=u=v/2$. Equivalently, if $v>0$,The same bound holds at $v=0$ by continuity. Therefore $I(X;Y)\le h_2(v/2)-v/2$, with equality for symmetric outer input probabilities. Writing $z=v/2\in [0,1/2]$, differentiate:The unique zero is $z=1/3$; strict concavity makes it the global maximum. Thus $v=2/3$ andThe optimum output is $(1/6,2/3,1/6)$.

Every row has Shannon entropy $1$, so $H(Y\mid X)=1$ for every input law. Since the output alphabet has three symbols, Gibbs inequality gives $H(Y)\le {\log }_{2}3$. The uniform input givesso it attains the upper bound. ThereforeUniform output is necessary for equality in the entropy bound, and the three displayed equations then force the uniform input, so this optimum input law is unique.

Let the input law again be $(s,t,u)$. The second output symbol has probability $1/2$ regardless of the input, and the two remaining output probabilities sum to $1/2$. Hencewith equality when the first and third output symbols each have probability $1/4$. The row entropies are $1,3/2,1$, soTake $t=0$ and $s=u=1/2$. The output is $(1/4,1/2,1/4)$ and both bounds are attained. ThereforeThe equality conditions also show uniqueness of the optimum input law. The middle row is the average of the outer rows and carries extra conditional entropy without introducing a new output law; removing a redundant input symbol from a channel explains why it need not be used.