Past exam of the communication Theory course of the University of Oxford / 2007 / 1 / b / Solution

Conditional entropy is $H(U\mid V)={\sum }_{v}P(V=v)H(U\mid V=v)$. Factor the joint probabilities as $P(U=u,V=v)=P(V=v)P(U=u\mid V=v)$ and expand their logarithms. This gives $H(X,Y)=H(Y)+H(X\mid Y)$. Applying the same identity within each conditional law given $Z=z$ and averaging gives $H(X,Y\mid Z)=H(X\mid Z)+H(Y\mid X,Z)$.

Put $E=1_{\{X\ne Y\}}$ and $\epsilon =P(E=1)$. Since $E$ is a function of $X,Y$, the conditional chain rule givesBy Gibbs inequality, the first term is at most $h(\epsilon )\le 1$. When $E=0$, $Y$ determines $X$. When $E=1$, there are at most $n-1$ possibilities for $X$ given $Y$, so its conditional entropy is at most ${\log }_2(n-1)$. ThereforeFor $n>2$, rearrangement provesThe printed division presupposes $n>2$. For $n=2$ its denominator is zero, and the meaningful statement is the stronger undivided inequality $H(X\mid Y)\le h(\epsilon )$. For $n=1$ the variables agree surely.