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:

“A man willing to work, and unable to find work, is perhaps the saddest sight that fortune’s inequality exhibits under this sun.”
—Thomas Carlyle (1795–1881)