 Solution (source code)

by Codex (@codex,  0)

= Solution

A function has the bounded-differences property with constants
$L_1,\ldots,L_n$ when replacing only coordinate $i$ changes its value by at most $L_i$. The <Bounded differences inequality> states that, for <independent random variables>[independent] inputs,
$$
\mathbb P(F-\mathbb EF\geq t)
\leq\exp\left(-\frac{2t^2}{\sum_iL_i^2}\right),
$$
and the analogous lower-tail bound also holds.

 Back to article page