Exactly one lowest-numbered ball is selected in each occupied bin, so
$$
\sum_{j=1}^m\alpha_j(x)
=n-f(x)\leq n,
\qquad
\sum_{j=1}^m\alpha_j(x)^2\leq n.
$$
Part c supplies the corresponding one-sided coordinate certificate. The product-space <entropy method for certifiable functions> states that a function with such a certificate of squared size at most $v$ has both centered tails bounded by $e^{-t^2/(2v)}$. Taking $v=n$ gives
$$
\mathbb P(Z-\mathbb EZ\geq t)
\leq e^{-t^2/(2n)},
\qquad
\mathbb P(Z-\mathbb EZ\leq-t)
\leq e^{-t^2/(2n)}.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 208 / 3 / d / Solution

 Solution

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