= Solution
Factoring a joint <probability> into successive conditional probabilities and taking the expected negative logarithm gives the <chain rule for conditional entropy>[chain rule for entropy]:
$$
H_n=\sum_{r=1}^nH(X_r\mid X_1,\ldots,X_{r-1}).
$$
At $r=1$ this means the unconditional <Shannon entropy>[entropy]. Removing conditioning can only increase each term by part (a), so $H_n\leq\sum_rH(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)$. Therefore
$$
\sum_rH(X_{-r}\mid X_r)=nH_n-\sum_rH(X_r)\leq(n-1)H_n.
$$
Divide by $n-1>0$ to obtain the required averaged inequality. The case $n=1$ is excluded precisely because that denominator vanishes.
Back to article page
