Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 2 / ii / Solution

Shearer's inequality states that if $X=(X_1,\dots ,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

Order the coordinates naturally. For every $F\in \mathcal{F}$, the chain rule for information entropy givesRemoving conditioning variables cannot decrease entropy, so every summand is at leastAfter summing over $F$, each index $i$ contributes at least $t$ times. A final application of the chain rule yieldswhich proves the lemma.