Martingales
Review of conditional probability
Martingales and Azuma's Inequality
Azuma's Inequality:
- Let [math]\displaystyle{ X_0,X_1,\ldots }[/math] be a martingale such that, for all [math]\displaystyle{ k\ge 1 }[/math],
- [math]\displaystyle{
|X_{k}-X_{k-1}|\le c_k,
}[/math]
Then
- [math]\displaystyle{ \begin{align}
\Pr\left[|X_n-X_0|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{k=1}^nc_k^2}\right).
\end{align} }[/math]
|
Corollary:
- Let [math]\displaystyle{ X_0,X_1,\ldots }[/math] be a martingale such that, for all [math]\displaystyle{ k\ge 1 }[/math],
- [math]\displaystyle{
|X_{k}-X_{k-1}|\le c,
}[/math]
Then
- [math]\displaystyle{ \begin{align}
\Pr\left[|X_n-X_0|\ge ct\sqrt{n}\right]\le 2 e^{-t^2/2}.
\end{align} }[/math]
|
Generalizations
Azuma's Inequality (general version):
- Let [math]\displaystyle{ Y_0,Y_1,\ldots }[/math] be a martingale with respect to the sequence [math]\displaystyle{ X_0,X_1,\ldots }[/math] such that, for all [math]\displaystyle{ k\ge 1 }[/math],
- [math]\displaystyle{
|Y_{k}-Y_{k-1}|\le c_k,
}[/math]
Then
- [math]\displaystyle{ \begin{align}
\Pr\left[|Y_n-Y_0|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{k=1}^nc_k^2}\right).
\end{align} }[/math]
|
The Method of Bounded Differences
Theorem (The method of averaged bounded differences):
- Let [math]\displaystyle{ X=(X_0,X_1,\ldots, X_n) }[/math] be arbitrary random variables and let [math]\displaystyle{ f }[/math] be a function of [math]\displaystyle{ X_0,X_1,\ldots, X_n }[/math] satisfying that, for all [math]\displaystyle{ 1\le i\le n }[/math],
- [math]\displaystyle{
|\mathbf{E}[f(X)\mid X_1,\ldots,X_i]-\mathbf{E}[f(X)\mid X_1,\ldots,X_{i-1}]|\le c_i,
}[/math]
- Then
- [math]\displaystyle{ \begin{align}
\Pr\left[|f(X)-\mathbf{E}[f(X)]|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{i=1}^nc_i^2}\right).
\end{align} }[/math]
|
Definition (Lipschitz condition):
- A function [math]\displaystyle{ f(x_1,\ldots,x_n) }[/math] satisfies the Lipschitz condition, if for any [math]\displaystyle{ x_1,\ldots,x_n }[/math] and any [math]\displaystyle{ y_i }[/math],
- [math]\displaystyle{ \begin{align}
|f(x_1,\ldots,x_{i-1},x_i,x_{i+1},\ldots,x_n)-f(x_1,\ldots,x_{i-1},y_i,x_{i+1},\ldots,x_n)|\le 1.
\end{align} }[/math]
|
In other words, the function satisfies the Lipschitz condition if an arbitrary change in the value of any one argument does not change the value of the function by more than 1.
Corollary (Method of bounded differences):
- Let [math]\displaystyle{ X=(X_0,X_1,\ldots, X_n) }[/math] be independent random variables and let [math]\displaystyle{ f }[/math] be a function satisfying the Lipschitz condition.
- Then
- [math]\displaystyle{ \begin{align}
\Pr\left[|f(X)-\mathbf{E}[f(X)]|\ge t\right]\le 2\exp\left(-\frac{t^2}{2n}\right).
\end{align} }[/math]
|
Applications