McDiarmid inequality
= McDiarmid inequality
{c}
{wiki=McDiarmid's_inequality}
If $X_1,\ldots,X_n$ are <independent random variables> and $f$ has <bounded differences property>[bounded differences] constants $c_i$, then
$$
\mathbb P\bigl(f(X)-\mathbb Ef(X)\geq t\bigr)
\leq\exp\left(-\frac{2t^2}{\sum_i c_i^2}\right),
$$
and the same bound holds for the lower tail.