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 each [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]
|
Generalizations
The Method of Bounded Differences
Applications