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

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.