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_0,X_1,\ldots, X_n }[/math] be an arbitrary set of 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\mid X_1,\ldots,X_i]-\mathbf{E}[f\mid X_1,\ldots,X_{i-1}]|\le c_i,
}[/math]
- Then
- [math]\displaystyle{ \begin{align}
\Pr\left[|f-\mathbf{E}[f]|\ge t\right]\le 2\exp\left(-\frac{t^2}{2\sum_{i=1}^nc_i^2}\right).
\end{align} }[/math]
|
Method of bounded differences:
- Let [math]\displaystyle{ 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-\mathbf{E}[f]|\ge t\right]\le 2\exp\left(-\frac{t^2}{2n}\right).
\end{align} }[/math]
|
Applications