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

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.