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

The channel matrix has entries $M_{xy}=P(Y=y\mid X=x)$, with nonnegative entries and each row summing to one. For an input distribution $\pi$, it induces the joint law $P(X=x,Y=y)={\pi }_x{M}_{xy}$. Its capacity in bits per use isOn finite alphabets the maximum exists by continuity on the compact probability simplex.

Gibbs inequality makes mutual information nonnegative, so $C\ge 0$. The two conditional-Shannon entropy expressions giveEach Shannon entropy is bounded by the base-two logarithm of its alphabet size. Maximizing over the input distribution therefore gives $\boxed{0\le C\le {\log }_{2}m}$ for the smaller size $m$.

Exchanging the first and third inputs, together with the corresponding outputs, leaves the channel unchanged. Concavity therefore shows that averaging an input distribution with its exchanged distribution cannot reduce mutual information. We may take input probabilities $(a,1-2a,a)$.

For $p<1$, put $b=1-p$ and $t=2ab$, so $0\le t\le b$. The output distribution is $(t/2,1-t,t/2)$ and the mean conditional output Shannon entropy is $2ah(p)=th(p)/b$. HenceIts strict concavity gives the unique stationary value $t_{\ast }=[1+2^{h(p)/b-1}{]}^{-1}$. This lies in the allowed interval: for $0<p<1$, the derivative at $t=b$ is $({\log }_{2}p+b)/b<0$, while it tends to positive infinity at zero. At $p=0$ the stationary value is $2/3<1$ directly. Consequently an achieving input distribution isThe resulting capacity is $C={\log }_2(1+2^{1-h(p)/(1-p)})$. In particular at $p=1/2$, $a=1/3$ andAt $p=1$ all outputs are the middle symbol, so $C=0$ and every input distribution achieves it; the divided formula is not used at that endpoint.