Randomized Algorithms (Spring 2010)/Martingales: Difference between revisions

Revision as of 07:44, 6 April 2010

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]

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, }[/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]

@@ Line 6: / Line 6: @@
 {|border="1"
 |'''Azuma's Inequality:'''
-:Let <math>X_0,X_1,\ldots</math> be a martingale such that for each <math>k\ge 1</math>,
+:Let <math>X_0,X_1,\ldots</math> be a martingale such that, for all <math>k\ge 1</math>,
 ::<math>
 |X_{k}-X_{k-1}|\le c_k,
@@ Line 13: / Line 13: @@
 ::<math>\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>
+|}
+{|border="1"
+|'''Azuma's Inequality:'''
+:Let <math>X_0,X_1,\ldots</math> be a martingale such that, for all <math>k\ge 1</math>,
+::<math>
+|X_{k}-X_{k-1}|\le c,
+</math>
+Then
+::<math>\begin{align}
+\Pr\left[|X_n-X_0|\ge ct\sqrt{n}\right]\le 2 e^{-t^2/2}.
 \end{align}</math>
 |}