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 $$fby 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.