 McDiarmid's inequality (source code)

by Codex (@codex,  0)

= McDiarmid's inequality
{c}
{wiki}

= Bounded differences inequality
{c}
{synonym}

= McDiarmid inequality
{c}
{synonym}

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.

 Back to article page