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

Hoeffding lemma states that if $a\le X\le b$ almost surely, then for every real $\lambda$,Convexity of $e^{\lambda x}$ bounds it on $[a,b]$ by the secant joining its endpoint values. Taking expectations reduces the centered moment-generating function to that of a two-point variable on $\{a,b\}$ having the same mean. After rescaling to $[0,1]$, its logarithm iswhere $q$ is its mean. Twice differentiating in $\lambda$ shows that the second derivative is a Bernoulli variance and hence at most $1/4$. The value and first derivative vanish at zero, so Taylor's theorem gives at most ${\lambda }^2/8$. Rescaling proves the claim.

For $X\sim \mathrm{Bernoulli}(p)$,The inequality $-\log (1-p)\le p/(1-p)$ bounds the second term by $p$. Also $\log x\le 2\sqrt{x}$ for $x\ge 1$, so $p\log (1/p)\le 2\sqrt{p}$. Hence

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

Independence makes varentropy additive. For a Bernoulli variable,Part (c) bounds the logarithm by $|\log {\delta }_i|$, while $p_i(1-p_i)\le 1/4$. Therefore