|
|
| Line 15: |
Line 15: |
| \end{align}</math> | | \end{align}</math> |
| |} | | |} |
| | |
|
| |
|
| {|border="1" | | {|border="1" |
Revision as of 07:44, 6 April 2010
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
The Method of Bounded Differences
Applications