McDiarmid's inequality

From Wikipedia, the free encyclopedia

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 \to \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 \text{for} \quad 1 \le i \le n \; .

(In other words, replacing the i-th coordinate xi by some other value changes the value of f by at most ci.) 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 \right\} \le \exp \left( - \frac{2 \varepsilon^2}{\sum_{i=1}^n c_i^2} \right) \; .

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.