 Solution (source code)

by Codex (@codex,  0)

= Solution

The <Chernoff bound> and part (b) give
$$
\mathbb P(f(X)\geq t)
\leq e^{-\lambda_*t}F(\lambda_*)
\leq3e^{-t/\sqrt{C_P(X)}}.
$$
Apply the same argument to $-f$ and use the <union bound> to obtain
$$
\mathbb P(|f(X)|\geq t)
\leq6e^{-t/\sqrt{C_P(X)}}.
$$

 Back to article page