Azuma’s Inequality
The Chernoff bound gives the concentration of sums of independent random variables. The concentration result can be generalized to martingales.
Martingales and Azuma’s Inequality
A sequence of random variables \(X_0, X_1, \ldots, X_n\) is called a martingale if
\[
{\bf E}[X_i\mid X_{i-1}, \ldots, X_{0}] = X_{i-1}.
\]
Let \(Y_i = X_i – X_{i-1}\); then \({\bf E}[Y_i\mid X_{i-1},\ldots, X_{0}] = 0\).
Theorem (Azuma’s Inequality) Let \(X_0, X_1,\ldots, X_n\) be a martingale, and \(Y_i = X_i – X_{i-1}\). If there exists constant \(c_i > 0\) such that \(|Y_i| \leq c_i\), then for any \(\lambda > 0\),
\[
{\bf Pr}[X_n – X_0 \geq \lambda] \leq \exp\left( -\frac{\lambda^2}{2\sum_{i=1}^n c_i^2 } \right),
\]
and
\[
{\bf Pr}[X_n – X_0 \leq -\lambda] \leq \exp\left( -\frac{\lambda^2}{2\sum_{i=1}^n c_i^2 } \right).
\]
First, we need the following lemma.
Lemma Let \(Y\) be a random variable such that \({\bf E}[Y] = 0\) and \(|Y| \leq c\) for some constant \(c > 0\). Then for any \(t > 0\), it holds that \({\bf E}[e^{tY}] \leq e^{t^2c^2/2}\).
The proof follows from the convexity of \(f(x) = e^{tx}\). For any \(|x| \leq c\), we have
\[
e^{tx} \leq \frac{1}{2c} (e^{tc} – e^{-tc}) x + \frac{1}{2}(e^{tc} + e^{-tc}).
\]
Taking expectations on both sides, we have
\[
{\bf E}[e^{tY}] \leq \frac{1}{2}(e^{tc} + e^{-tc}) = e^{t^2c^2/2}.
\]
Here using Taylor series \(e^{x} = \sum^{\infty}_{n=0} \frac{x^n}{n!}\), we have
\[
\frac{1}{2}(e^x + e^{-x}) = \sum_{n=0}^{\infty} \frac{x^{2n}}{(2n)!}
\leq \sum_{n=0}^{\infty} \frac{x^{2n}}{2^n n!} = e^{x^2/2}
\]
Now we are ready to prove Azuma’s inequality. First,
\[
{\bf E}[e^{tY_i} \mid X_{i-1},\ldots, X_1] \leq e^{t^2c_i^2/2}.
\]
This gives a constant bound independent of the conditioning. By backward induction,
\[
{\bf E}[e^{tX_i}] ={\bf E}[e^{t(Y_i + X_{i-1})}] =
{\bf E}[e^{t X_{i-1}} \cdot {\bf E}[e^{t Y_i}\mid X_{i-1},\ldots, X_1]] \\
\leq {\bf E}[e^{t X_{i-1}} ] \cdot e^{t^2c_i^2/2}=
e^{t^2 \sum_{j=1}^{i}c_j^2/2} {\bf E}[e^{tX_0}].
\]
Therefore, by Markov’s inequality, we have
\[
{\bf Pr} [ X_n – X_0 \geq \lambda ]
= {\bf Pr} [ e^{t(X_n – X_0)} \geq e^{\lambda t} ] \\
\leq e^{-\lambda t} {\bf E}[e^{t(X_n – X_0)}]
\leq e^{-\lambda t + t^2 \sum_{j=1}^{n}c_j^2/2}
\]
The above holds for any \(t > 0\). Taking \(t = \lambda / \sum_{j=1}^{n}c_j^2\), we complete the proof.
Application: Coin Tossing
Let \(Z_1,\ldots, Z_n\) be a sequence of independent variables taking two values -1 and 1 with equal probability (random coin tossing). Let \(X_0=0\) and \(X_i = \sum_{j=1}^i Z_i\) for \(i= 1, \ldots, n\). Then \(X_0,\ldots, X_n\) is a martingale.
By Azuma’s inequality, for any \(\lambda > 0\)
\[
{\bf Pr}[X_n \geq \lambda] \leq \exp(-\frac{\lambda^2}{2n}).
\]
Note that, in this case, \(X_i\) is a sum of independent variables; a similar bound can be derived using the Chernoff bound.