McDiarmid's inequality

McDiarmid's inequality, named after Colin McDiarmid, is a result in probability theory that gives an upper bound on the probability for the value of a function depending on multiple independent random variables to deviate from its expected value. It is a generalization of Hoeffding's inequality.

Let $X\_1,\; X\_2,\; dots,\; X\_n$ be independent random variables taking values in a set $A$, and assume that$f:A^n\; o\; Bbb\{R\}$ is a function satisfying

$sup\_\{x\_1,x\_2,dots,x\_n,\; hat\; x\_i\}\; |f(x\_1,x\_2,dots,x\_n)\; -\; f(x\_1,x\_2,dots,x\_\{i-1\},hat\; x\_i,\; x\_\{i+1\},\; dots,\; x\_n)|\; le\; c\_i\; qquad\; ext\{for\}\; quad\; 1\; le\; i\; le\; n\; ;\; .$

(In other words, replacing the $i$-th coordinate $x\_i$ by some other value changes the value of $f$by at most $c\_i$.) Then for any $varepsilon\; >\; 0$,

$Pr\; left\{\; f(X\_1,\; X\_2,\; dots,\; X\_n)\; -\; E\; [f(X\_1,\; X\_2,\; dots,\; X\_n)]\; ge\; varepsilon\; ight\}\; le\; exp\; left(\; -\; frac\{2\; varepsilon^2\}\{sum\_\{i=1\}^n\; c\_i^2\}\; ight)\; ;\; .$

The Hoeffding's inequality is obtained, as a special case, by applying McDiarmid's inequality to the function $f(x\_1,\; x\_2,\; dots,\; x\_n)\; =\; sum\_\{i=1\}^n\; x\_i$.