Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 208 / 1 / c / Solution

Put $q_i=\min (p_i,1-p_i)$. Applying part (b) after possibly replacing $X_i$ by $1-X_i$ gives $H(X_i)\le 2\sqrt{q_i}+q_i$. If $q_i<{\delta }_i$, then, because $0<{\delta }_i<1$, this is less than $3\sqrt{{\delta }_i}$, contradicting the assumption. Thus $p_i,1-p_i\ge {\delta }_i$.

The centered variablesare independent and have mean zero. Their two possible values differ byApplying Hoeffding inequality to ${\sum }_i{Y}_i$ gives