= Solution
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)}.
$$
Back to article page
