= Solution
<Shearer's inequality> states that if $X=(X_1,\ldots,X_n)$ is a discrete <random vector> and $\mathcal F$ is a collection of subsets of $[n]$ in which every index occurs at least $t$ times, then
$$
\boxed{tH(X)\leq\sum_{F\in\mathcal F}H(X_F)}.
$$
Order the coordinates naturally. For every $F\in\mathcal F$, the <chain rule for information entropy> gives
$$
H(X_F)=\sum_{i\in F}H\left(X_i\mid X_j:j\in F,\ j<i\right).
$$
Removing conditioning variables cannot decrease entropy, so every summand is at least
$$
H(X_i\mid X_1,\ldots,X_{i-1}).
$$
After summing over $F$, each index $i$ contributes at least $t$ times. A final application of the chain rule yields
$$
\sum_{F\in\mathcal F}H(X_F)
\geq t\sum_{i=1}^nH(X_i\mid X_1,\ldots,X_{i-1})
=tH(X),
$$
which proves the lemma.
Back to article page
