Martingale Theory

Let $(M_n)$ be a martingale with bounded increments: $|M_k - M_{k-1}| \leq c_k$ almost surely for $k = 1, \ldots, n$. Then for any $t > 0$:

$\Pr[M_n - M_0 \geq t] \leq \exp\!\left(-\frac{t^2}{2\sum_{k=1}^n c_k^2}\right)$

$\Pr[|M_n - M_0| \geq t] \leq 2\exp\!\left(-\frac{t^2}{2\sum_{k=1}^n c_k^2}\right)$

If all $c_k = c$ (equal bounds), this simplifies to $\Pr[|M_n - M_0| \geq t] \leq 2\exp(-t^2/(2nc^2))$.

A martingale with bounded increments (each step moves by at most $c_k$) cannot deviate far from its starting point with high probability. The deviation is controlled by $\sqrt{\sum c_k^2}$ --- the "diffusion scale" of the random walk. This is the martingale analogue of Hoeffding's inequality for sums of independent bounded random variables.

Azuma-Hoeffding is the engine behind McDiarmid's inequality. If $f(X_1, \ldots, X_n)$ has bounded differences (changing $X_i$ changes $f$ by at most $c_i$), then the Doob martingale $Z_i = \mathbb{E}[f \mid X_1, \ldots, X_i]$ has bounded increments $|D_i| \leq c_i$, and Azuma-Hoeffding gives:

$\Pr[f(X) - \mathbb{E}[f(X)] \geq t] \leq \exp\!\left(-\frac{2t^2}{\sum c_i^2}\right)$

This is how generalization bounds, Rademacher complexity concentration, and many other ML results are proved.

Azuma-Hoeffding uses only the worst-case increment bound $c_k$. If the increments are typically much smaller than $c_k$ (small variance but bounded range), the bound is loose. The Freedman inequality below is tighter in this case because it uses the variance of the increments.

Let $(M_n)_{n \geq 0}$ be a supermartingale with $\sup_n \mathbb{E}[M_n^-] < \infty$ (equivalently, for a non-negative supermartingale, no condition is needed). Then there exists a random variable $M_\infty$ with $\mathbb{E}[|M_\infty|] < \infty$ such that:

$M_n \to M_\infty \quad \text{almost surely}$

For a martingale bounded in $L^2$ ($\sup_n \mathbb{E}[M_n^2] < \infty$), the convergence also holds in $L^1$: $\mathbb{E}[|M_n - M_\infty|] \to 0$.

A non-negative supermartingale is a "wealth process" for a gambler playing unfavorable games: expected wealth decreases over time, and the wealth cannot go below zero. Such a process must eventually settle down --- it cannot keep fluctuating forever because it has no expected upward drift and it is bounded below. The almost-sure limit captures the gambler's long-run fortune.

For bounded $L^2$ martingales, the convergence is stronger: the sequence not only converges pointwise but the expected deviation from the limit goes to zero.

In ML theory, martingale convergence appears in:

• Stochastic approximation: SGD with decreasing step size produces iterates whose conditional expectations form a supermartingale (under appropriate conditions), so convergence is guaranteed
• Online learning: the regret of certain algorithms, properly normalized, is a supermartingale that converges, giving per-round regret bounds
• Bayesian consistency: posterior beliefs, viewed as a martingale indexed by the amount of data, converge to the truth under regularity conditions

Almost-sure convergence does not imply $L^1$ convergence in general. The classic counterexample: let $M_n$ be 0 with probability $1 - 1/n$ and $n$ with probability $1/n$, arranged so $\mathbb{E}[M_n] = 1$ for all $n$. Then $M_n \to 0$ a.s. But $\mathbb{E}[M_n] = 1 \not\to 0$. For $L^1$ convergence, you need uniform integrability.

Let $(M_n)$ be a martingale and $\tau$ a stopping time with respect to $(\mathcal{F}_n)$. If $\tau \leq N$ almost surely for some constant $N$ (bounded stopping time), then:

$\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$

More generally, if $\tau$ is not bounded but: (a) $\mathbb{E}[\tau] < \infty$, and (b) there exists $c$ such that $\mathbb{E}[|M_{n+1} - M_n| \mid \mathcal{F}_n] \leq c$, then $\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$.

You cannot beat a fair game by choosing when to stop. If the game is fair at every step ($\mathbb{E}[M_{n+1} | \mathcal{F}_n] = M_n$), then your expected payoff when you stop equals your starting capital, no matter how cleverly you choose when to stop (as long as you must stop in bounded time).

The caveat "bounded time" is critical. With unbounded stopping times, you can have $\mathbb{E}[M_\tau] \neq \mathbb{E}[M_0]$ --- the classic example is the doubling strategy in gambling, which requires infinite credit.

Optional stopping is used in sequential analysis and online learning where you must decide when to stop based on observed data. In sequential hypothesis testing (Wald's SPRT), the likelihood ratio process is a martingale, and optional stopping gives error probability guarantees. In anytime-valid confidence sequences, martingale constructions provide confidence bounds that hold at arbitrary data- dependent stopping times.

The boundedness condition is not a technicality. The simple random walk $M_n = \sum_{i=1}^n X_i$ (with $X_i = \pm 1$ equally likely) is a martingale with $\mathbb{E}[M_0] = 0$. Let $\tau = \inf\{n : M_n = 1\}$. Then $M_\tau = 1$ always, so $\mathbb{E}[M_\tau] = 1 \neq 0 = \mathbb{E}[M_0]$. The problem: $\tau$ is not bounded (and $\mathbb{E}[\tau] = \infty$).

Let $(M_n)$ be a martingale with $|D_k| = |M_k - M_{k-1}| \leq R$. Define the predictable quadratic variation:

$W_n = \sum_{k=1}^n \mathbb{E}[D_k^2 \mid \mathcal{F}_{k-1}] = \sum_{k=1}^n \text{Var}(D_k \mid \mathcal{F}_{k-1})$

Then for any $t > 0$ and $v > 0$:

$\Pr[M_n - M_0 \geq t \text{ and } W_n \leq v] \leq \exp\!\left(-\frac{t^2/2}{v + Rt/3}\right)$

Azuma-Hoeffding uses only the worst-case increment bound $R$. But if the increments are typically much smaller (low conditional variance), the martingale concentrates much better than Azuma-Hoeffding predicts. Freedman's inequality captures this by depending on the actual cumulative conditional variance $W_n$ rather than the worst-case bound $nR^2$.

When $v \gg Rt$: the bound becomes $\exp(-t^2/(2v))$, a Gaussian-type tail (sub-Gaussian with parameter $v$). When $Rt \gg v$: the bound becomes $\exp(-3t/(2R))$, a Poisson-type tail (sub-exponential).

Freedman's inequality is the variance-sensitive analogue of Azuma-Hoeffding. It is tighter whenever the conditional variances are much smaller than the worst-case increment bounds --- which is common in practice.

In ML theory: when proving regret bounds for online learning algorithms, the per-round loss differences are bounded but often have low variance (the algorithm makes mostly good predictions). Freedman gives tighter regret bounds than Azuma in these cases.

The bound requires knowing (or bounding) the predictable quadratic variation $W_n$, which may itself be random. In practice, you often bound $W_n$ by a deterministic quantity and then the Freedman bound reduces to a variance-sensitive version of Azuma.