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:

“The doctrine of equality!... But there exists no more poisonous poison: for it seems to be preached by justice itself, while it is the end of justice.... “Equality for equals, inequality for unequals”Mthat would be the true voice of justice: and, what follows from it, “Never make equal what is unequal.””
—Friedrich Nietzsche (1844–1900)