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

For a finite joint distribution, the mutual information isZero-probability terms contribute zero. It measures the reduction in uncertainty about one variable upon observing the other.

A discrete memoryless channel has discrete input/output alphabets and a fixed transition matrix $W(y\mid x)$. Over successive uses it obeysThus the output at a use depends on that input and no other channel history. Its channel capacity isin bits per use for base-two logarithms. On finite alphabets the maximum exists by continuity on the probability simplex; for more general discrete alphabets one uses a supremum.

Fix the channel matrix $W$. The mixed input induces the mixed output $q_3=\lambda q_1+(1-\lambda )q_2$. The concavity of information entropy impliesFor completeness, the difference is $\lambda D(q_1\Vert q_3)+(1-\lambda )D(q_2\Vert q_3)\ge 0$ by Gibbs inequality, including zero coordinates with the usual conventions.

On the other hand, conditional output entropy is linear in the input law:Subtracting gives the concavity of mutual information in the input distribution:This makes maximizing mutual information over the input probability simplex a concave optimization problem: a local maximum is global. It also justifies averaging input distributions over channel symmetries when searching for an optimum, since symmetry averaging cannot lower the achieved mutual information. The channel itself is held fixed throughout.

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.