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

Use the convention $0{\log }_{2}0=0$. On the positive support of $p$, the given logarithm inequality givesThe logarithm is strictly concave, so its supporting line at one has equality only there. More explicitly, the given global bound forces $c=1/{\log }_{e}2$ by differentiation at one, and $x-1-{\log }_{e}x$ vanishes only at one. Equality above therefore requires $p_r=q_r$ on the positive support, and no mass of $q$ outside it. Thus equality holds exactly when $p=q$.

For the uniform distribution $q_r=1/n$, the divergence is $D(p,q)={\log }_{2}n-H(p)$. Its nonnegativity gives $\boxed{H(p)\le {\log }_{2}n}$, with equality precisely for the uniform law.

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.

Independence gives $P(X=Y)={\sum }_r{p}_r{q}_r={\mathbb{E}}_p[2^{{\log }_2{q}_X}]$. The given exponential convexity inequality therefore yieldsTaking complementary probabilities provesThe strict positivity of the entries of $q$ makes all logarithms appearing in this finite expectation well defined.