Limitation of the vanilla Azuma's inequality

Note that the vanilla Azuma's inequality requires symmetric bounds on martingale increments, i.e. ${\displaystyle -c_{t}\leq X_{t}-X_{t-1}\leq c_{t}}$. So, if known bound is asymmetric, e.g. ${\displaystyle a_{t}\leq X_{t}-X_{t-1}\leq b_{t}}$, to use Azuma's inequality, one need to choose ${\displaystyle c_{t}=\max(|a_{t}|,|b_{t}|)}$ which might be a waste of information on the boundedness of ${\displaystyle X_{t}-X_{t-1}}$. However, this issue can be resolved and one can obtain a tighter probability bound with the following general form of Azuma's inequality.

Statement

Let ${\displaystyle \left\{X_{0},X_{1},\cdots \right\}}$ be a martingale (or supermartingale) with respect to filtration ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$. Assume there are predictable processes ${\displaystyle \left\{A_{0},A_{1},\cdots \right\}}$ and ${\displaystyle \left\{B_{0},B_{1},\dots \right\}}$ with respect to ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$, i.e. for all ${\displaystyle t}$, ${\displaystyle A_{t},B_{t}}$ are ${\displaystyle {\mathcal {F}}_{t-1}}$-measurable, and constants ${\displaystyle 0<c_{1},c_{2},\cdots <\infty }$ such that

${\displaystyle A_{t}\leq X_{t}-X_{t-1}\leq B_{t}\quad {\text{and}}\quad B_{t}-A_{t}\leq c_{t}}$

almost surely. Then for all ${\displaystyle \epsilon >0}$,

${\displaystyle {\text{P}}(X_{n}-X_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Since a submartingale is a supermartingale with signs reversed, we have if instead ${\displaystyle \left\{X_{0},X_{1},\dots \right\}}$ is a martingale (or submartingale),

${\displaystyle {\text{P}}(X_{n}-X_{0}\leq -\epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

If ${\displaystyle \left\{X_{0},X_{1},\dots \right\}}$ is a martingale, since it is both a supermartingale and submartingale, by applying union bound to the two inequalities above, we could obtain the two-sided bound:

${\displaystyle {\text{P}}(|X_{n}-X_{0}|\geq \epsilon )\leq 2\exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Proof

We will prove the supermartingale case only as the rest are self-evident. By Doob decomposition, we could decompose supermartingale ${\displaystyle \left\{X_{t}\right\}}$ as ${\displaystyle X_{t}=Y_{t}+Z_{t}}$ where ${\displaystyle \left\{Y_{t},{\mathcal {F}}_{t}\right\}}$ is a martingale and ${\displaystyle \left\{Z_{t},{\mathcal {F}}_{t}\right\}}$ is a nonincreasing predictable sequence (Note that if ${\displaystyle \left\{X_{t}\right\}}$ itself is a martingale, then ${\displaystyle Z_{t}=0}$). From ${\displaystyle A_{t}\leq X_{t}-X_{t-1}\leq B_{t}}$, we have

${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$

Applying Chernoff bound to ${\displaystyle Y_{n}-Y_{0}}$, we have for ${\displaystyle \epsilon >0}$,

${\displaystyle {\begin{aligned}{\text{P}}(Y_{n}-Y_{0}\geq \epsilon )&\leq {\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} [e^{s(Y_{n}-Y_{0})}]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n}(Y_{t}-Y_{t-1})\right)\right]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n-1}(Y_{t}-Y_{t-1})\right)\mathbb {E} \left[\exp \left(s(Y_{n}-Y_{n-1})\right)\mid {\mathcal {F}}_{n-1}\right]\right]\end{aligned}}}$

For the inner expectation term, since

(i) ${\displaystyle \mathbb {E} [Y_{t}-Y_{t-1}\mid {\mathcal {F}}_{t-1}]=0}$ as ${\displaystyle \left\{Y_{t}\right\}}$ is a martingale;

(ii) ${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$;

(iii) ${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}}$ and ${\displaystyle -(Z_{t}-Z_{t-1})+B_{t}}$ are both ${\displaystyle {\mathcal {F}}_{t-1}}$-measurable as ${\displaystyle \left\{Z_{t}\right\}}$ is a predictable process;

(iv) ${\displaystyle B_{t}-A_{t}\leq c_{t}}$;

by applying Hoeffding's lemma^{[note 1]}, we have

${\displaystyle \mathbb {E} \left[\exp \left(s(Y_{t}-Y_{t-1})\right)\mid {\mathcal {F}}_{t-1}\right]\leq \exp \left({\frac {s^{2}(B_{t}-A_{t})^{2}}{8}}\right)\leq \exp \left({\frac {s^{2}c_{t}^{2}}{8}}\right).}$

Repeating this step, one could get

${\displaystyle {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq {\underset {s>0}{\min }}\ e^{-s\epsilon }\exp \left({\frac {s^{2}\sum _{t=1}^{n}c_{t}^{2}}{8}}\right).}$

Note that the minimum is achieved at ${\displaystyle s={\frac {4\epsilon }{\sum _{t=1}^{n}c_{t}^{2}}}}$, so we have

${\displaystyle {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

Finally, since ${\displaystyle X_{n}-X_{0}=(Y_{n}-Y_{0})+(Z_{n}-Z_{0})}$ and ${\displaystyle Z_{n}-Z_{0}\leq 0}$ as ${\displaystyle \left\{Z_{n}\right\}}$ is nonincreasing, so event ${\displaystyle \left\{X_{n}-X_{0}\geq \epsilon \right\}}$ implies ${\displaystyle \left\{Y_{n}-Y_{0}\geq \epsilon \right\}}$, and therefore

${\displaystyle {\text{P}}(X_{n}-X_{0}\geq \epsilon )\leq {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).\square }$

Remark

Note that by setting ${\displaystyle A_{t}=-c_{t},B_{t}=c_{t}}$, we could obtain the vanilla Azuma's inequality.

Note that for either submartingale or supermartingale, only one side of Azuma's inequality holds. We can't say much about how fast a submartingale with bounded increments rises (or a supermartingale falls).

This general form of Azuma's inequality applied to the Doob martingale gives McDiarmid's inequality which is common in the analysis of randomized algorithms.