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