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, but the two constants are not obtained by naive chaining. McDiarmid's inequality is derived from Azuma-Hoeffding applied to the Doob martingale $M_i = \mathbb{E}[f(X) \mid X_1, \ldots, X_i]$. Under the bounded-differences condition, the Doob increments $D_i = M_i - M_{i-1}$ satisfy the conditional range condition $\sup_{x_i, x_i'} |D_i|_{X_{i-1} = x_{i-1}} \leq c_i$, not merely $|D_i| \leq c_i$. Hoeffding's lemma for bounded-range random variables gives a factor-of-4 improvement over the naive absolute-value bound, yielding the McDiarmid constant:

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

This is NOT the same as the Azuma constant $\exp(-t^2/(2\sum c_k^2))$; they differ by a factor of 4 inside the exponent. A student who naively plugs $c_k = c_i$ into the Azuma bound above will get a constant that is 4x too loose. 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$ (in particular, a non-negative supermartingale is a special case since $M_n^- = 0$). 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: in the Robbins-Monro framework, SGD with step sizes satisfying $\sum_t \eta_t = \infty$ and $\sum_t \eta_t^2 < \infty$ has iterates that, under standard regularity, generate a non-negative almost-supermartingale to which the Robbins-Siegmund (1971) lemma applies, yielding almost-sure convergence to a stationary point
• 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 $(X_n)$ be a non-negative submartingale. For any $\lambda > 0$:

$\Pr\!\left(\max_{0 \leq k \leq n} X_k \geq \lambda\right) \leq \frac{\mathbb{E}[X_n]}{\lambda}$

This is the martingale analogue of Markov's inequality. Markov's inequality bounds the probability that a single non-negative random variable exceeds a threshold by its mean divided by the threshold. Doob's weak maximal inequality gives the same kind of tail control for the running maximum of a submartingale, using only the terminal expectation.

The weak maximal form is the version used when a proof needs a uniform-in-time tail bound rather than a fixed-time tail bound. It is a standard bridge from terminal martingale control to anytime-valid arguments, stopping-time estimates, and concentration proofs where the path's supremum matters.

The non-negativity and submartingale hypotheses are doing real work. Without them, the running maximum can be large even when the terminal value has small expectation, so the Markov-style ratio no longer controls the event. This weak inequality controls a tail probability; it does not by itself give an $L^p$ norm bound for the maximum.

Let $(X_n)$ be a non-negative submartingale. For $p > 1$, the $L^p$ maximal inequality gives:

$\mathbb{E}\!\left[\left(\max_{0 \leq k \leq n} X_k\right)^p\right] \leq \left(\frac{p}{p-1}\right)^p \mathbb{E}[X_n^p]$

The weak maximal inequality controls the probability of crossing one threshold. The $L^p$ maximal inequality upgrades that into moment control: if the terminal variable has a finite $p$th moment, then the whole path's maximum has a finite $p$th moment with an explicit constant.

The $L^p$ form is the stronger norm estimate used in convergence theorems, empirical-process arguments, and stochastic analysis. It turns terminal $L^p$ control into pathwise supremum control, which is exactly what many uniform-in-time estimates need.

The constant $(p/(p-1))^p$ diverges as $p \downarrow 1$, which is why this is not an $L^1$ maximal theorem. At $p = 1$, the right replacement is the weak maximal inequality above, not a strong $L^1$ bound with the same shape.

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]$

A useful sufficient condition for unbounded stopping times is: (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$, which imply $\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$ (see Williams, Probability with Martingales §10.10). Other non-equivalent sufficient conditions include: (i) uniform integrability of the stopped sequence $(M_{\tau \wedge n})$, or (ii) a dominating bound $|M_{\tau \wedge n}| \leq Y$ with $\mathbb{E}[Y] < \infty$ (dominated convergence). None of these is strictly "more general" than the others.

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.