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

For finite-valued random vectors, the conditional entropy is the average of the entropies of the conditional distributions:Use $0{\log }_{2}0=0$ and omit zero-probability conditioning events. Equivalently,The base two makes all information quantities measured in bits; changing the logarithm base scales them by a positive constant and preserves the inequalities.

Apply Gibbs inequality to the joint distribution and the product of its marginals. Restrict to the Cartesian product of their positive supports, so the reference probabilities are strictly positive as the supplied inequality requires. Expanding givesThis proves the second inequality. For the first, apply the same argument to the conditional joint distribution of $(X,Z)$ for each $y$ with $p_Y(y)>0$, and average with those probabilities:Here the conditional support restriction again removes zero marginal probabilities. ThusThe nonnegative differences are conditional mutual information and mutual information, respectively.

Factoring a joint probability into successive conditional probabilities and taking the expected negative logarithm gives the chain rule for entropy:At $r=1$ this means the unconditional entropy. Removing conditioning can only increase each term by part (a), so $H_n\le {\sum }_{r}H(X_r)$.

Write $X_{-r}$ for the vector omitting coordinate $r$. Another application of the chain rule gives $H(X_{-r}\mid X_r)=H_n-H(X_r)$. ThereforeDivide by $n-1>0$ to obtain the required averaged inequality. The case $n=1$ is excluded precisely because that denominator vanishes.

The chain rule for entropy, with $X_r$ placed last, givesSince $X_{-r}$ includes all the preceding coordinates, conditioning monotonicity givesThis proves the first assertion for every $r$, including $r=1$. Sum over $r$: the conditional terms on the right sum to $H_n$ by the ordinary chain rule. ThusThis is Han's entropy inequality.

For each $r$, conditioning on all the other coordinates gives no greater conditional entropy than conditioning only on the preceding ones. Summing and using the chain rule for entropy gives directlyEquivalently, the left side is $n{H}_n-{\sum }_{r}H(X_{-r})$, so the same conclusion follows from Han's entropy inequality. The direct proof also covers $n=1$, interpreting conditioning on an empty vector as no conditioning.