Lagmental Vicfred

Azuma--Hoeffding Controls Martingales with Bounded Differences by Vicfred

tags: mathematics, concentration inequalities, tail bounds, martingales

A martingale whose increments are uniformly bounded has Gaussian-shaped tails. A small computation will anchor the general statement before the abstraction takes over.

Definitions first

Tail bounds convert information about the moment-generating function \(M_X(\lambda)=\mathbf E[e^{\lambda X}]\) into estimates for \(\mathbf P(X\ge t)\). Stronger assumptions produce exponentially sharper bounds.

$$ (M_k,\mathcal F_k)_{k=0}^{n}\ \text{martingale},\qquad|M_k-M_{k-1}|\le c_k $$

I keep the defining relation \(\mathsf D\) above the derived relation \(\mathsf C\). This exposes whether cancellation used \(x\ne0\) and whether the conclusion is canonical.

$$ \mathbf P(|M_n-M_0|\ge t)\le2\exp\!\left(-\frac{t^2}{2\sum_{k=1}^{n}c_k^2}\right) $$

A small case in full

This is the algebraic core of the note. Once this line is correct, the surrounding interpretation has something solid to refer to.

$$ \begin{aligned}D_k&=M_k-M_{k-1},\\\mathbf E[D_k\mid\mathcal F_{k-1}]&=0,\qquad|D_k|\le c_k.\end{aligned} $$

The reusable statement

The compact alignment is a local map of the argument: assumptions on the first row, consequence on the second. Any generalisation must preserve that dependency.

$$ \begin{aligned} \mathsf{D}\;&:\quad (M_k,\mathcal F_k)_{k=0}^{n}\ \text{martingale},\qquad|M_k-M_{k-1}|\le c_k,\\[5pt] \mathsf{C}\;&:\quad \mathbf P(|M_n-M_0|\ge t)\le2\exp\!\left(-\frac{t^2}{2\sum_{k=1}^{n}c_k^2}\right). \end{aligned} $$

A nearby false statement

The parameter must be optimized only over values where the moment-generating function exists. Independence and boundedness hypotheses are not interchangeable.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \mathbf P(|M_n-M_0|\ge t)\le2\exp\!\left(-\frac{t^2}{2\sum_{k=1}^{n}c_k^2}\right) \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Thu 10 August 2017. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.