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

The chain rule for information entropy and conditioning reduces entropy giveThus subadditivity of information entropy holds for two finitely valued random variables. Applying this inequality to $(X_1,\dots ,X_{n-1})$ and $X_n$ and then inducting gives

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.

Choose $A$ uniformly from $\mathcal{A}$, and let $X_i=1_{\{i\in A\}}$. The characteristic vector of a set determines $A$, soFor $F\in \mathcal{F}$, the projected vector $X_F$ determines the intersection $A\cap F$ and therefore takes values in the trace of a set family $T_F(\mathcal{A})$. The maximum-entropy bound on a finite set givesEvery coordinate belongs to at least $t$ members of $\mathcal{F}$, so Shearer's inequality givesExponentiation proves the Shearer trace inequality