The lower-tail form of the <entropy method for certifiable functions> states that a unit-bounded-difference, $g$-certifiable nonnegative integer-valued function satisfies
$$
\log\mathbb E e^{-\lambda(Z-\mathbb EZ)}
\leq\frac{\lambda^2}{2}\mathbb E[g(Z)]
\qquad(\lambda\geq0).
$$
It follows by applying entropy tensorization to a minimal certificate: only its at most $g(Z)$ coordinates can contribute to the one-sided variance proxy, and changing any one contributes at most one.

The Chernoff bound therefore gives
$$
\mathbb P(Z-\mathbb EZ\leq-t)
\leq\inf_{\lambda>0}
\exp\!\left(-\lambda t+\frac{\lambda^2}{2}\mathbb E[g(Z)]\right).
$$
Choosing $\lambda=t/\mathbb E[g(Z)]$ proves
$$
\mathbb P(Z-\mathbb EZ\leq-t)
\leq\exp\!\left(-\frac{t^2}{2\mathbb E[g(Z)]}\right).
$$

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 208 / 3 / b / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-208/3/b/solution