For $S_i=[n]\setminus\{i\}$, the <chain rule for information entropy> gives
$$
H(X_{S_i})=\sum_{j\in S_i}H(X_j\mid X_{S_i\cap[j-1]}).
$$
Each summand is at least $H(X_j\mid X_1^{j-1})$ because <conditioning reduces entropy>. Summing over $i$, each $j$ occurs $n-1$ times:
$$
\sum_{i=1}^nH(X_{S_i})
\geq(n-1)\sum_{j=1}^nH(X_j\mid X_1^{j-1})
=(n-1)H(X_1^n).
$$
This is the required special case of <Shearer's inequality>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 224 / 2 / b / Solution

 Solution

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