= Solution
The coordinate-deletion functions from part c show that $Z$ is weakly self-bounding. Its negative centered moment-generating function therefore satisfies the <lower-tail concentration for a weakly self-bounding function> estimate
$$
\log\mathbb E e^{-\lambda(Z-\mathbb EZ)}
\leq\frac{\lambda^2\mathbb EZ}{2},
\qquad \lambda\geq0.
$$
Applying the <Chernoff bound>, for every $\lambda\geq0$,
$$
\mathbb P(Z-\mathbb EZ<-t)
\leq\exp\left(-\lambda t+\frac{\lambda^2\mathbb EZ}{2}\right).
$$
The exponent is minimized at $\lambda=t/\mathbb EZ$, giving
$$
\mathbb P(Z-\mathbb EZ<-t)
\leq\exp\left(-\frac{t^2}{2\mathbb EZ}\right).
$$
Back to article page
