<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.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-161/2/ii/solution