Doob Martingale - McDiarmid's Inequality

McDiarmid's Inequality

One common way of bounding the differences and applying Azuma's inequality to a Doob martingale is called McDiarmid's inequality. Suppose are independent and assume that satisfies

$\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 -th coordinate by some other value changes the value of by at most .)

It follows that

and therefore Azuma's inequality yields the following McDiarmid inequalities for any :

$\Pr \left\{ f(X_1, X_2, \dots, X_n) - E \ge \varepsilon \right\} \le \exp \left( - \frac{2 \varepsilon^2}{\sum_{i=1}^n c_i^2} \right)$

and

$\Pr \left\{ 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)$

and

$\Pr \left\{ |E - f(X_1, X_2, \dots, X_n)| \ge \varepsilon \right\} \le 2 \exp \left( - \frac{2 \varepsilon^2}{\sum_{i=1}^n c_i^2} \right). \;$

Read more about this topic: Doob Martingale

Famous quotes containing the word inequality:

“Nature is unfair? So much the better, inequality is the only bearable thing, the monotony of equality can only lead us to boredom.”
—Francis Picabia (1878–1953)