Azuma-Hoeffding Bound Diagnostics

What an Azuma–Hoeffding Bound Requires

An Azuma–Hoeffding calculation can look routine while relying on an increment assumption that has not actually been checked. The main diagnostics are precise: identify the filtration relative to which the process is a martingale, verify a conditional mean-zero statement, and determine whether the available bound controls the absolute size of each increment or only the width of its conditional range. Those two types of bounds lead to related but differently parameterized formulas.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(\mathcal{F}_k)_{k=0}^n$ be a filtration, meaning $\mathcal{F}_{k-1}\subseteq\mathcal{F}_k\subseteq\mathcal{F}$. An integrable process $(M_k)_{k=0}^n$ is adapted if $M_k$ is $\mathcal{F}_k$-measurable. It is a martingale with respect to this filtration if it is adapted and $\mathbb{E}[M_k\mid\mathcal{F}_{k-1}]=M_{k-1}$ almost surely for each $k\ge1$. Its increments are $D_k=M_k-M_{k-1}$. Thus the martingale condition is exactly $\mathbb{E}[D_k\mid\mathcal{F}_{k-1}]=0$ almost surely.

Theorem (Azuma–Hoeffding, increment forms): Suppose $(M_k)_{k=0}^n$ is an integrable martingale with respect to $(\mathcal{F}_k)$. If deterministic constants $c_k\ge0$ satisfy $|D_k|\le c_k$ almost surely, then for $x>0$, $$ \mathbb{P}(M_n-M_0\ge x)\le \exp\!\left(-\frac{x^2}{2\sum_{k=1}^n c_k^2}\right), $$ provided $\sum_k c_k^2>0$. If instead deterministic intervals $[a_k,b_k]$ satisfy $a_k\le D_k\le b_k$ almost surely, then $$ \mathbb{P}(M_n-M_0\ge x)\le \exp\!\left(-\frac{2x^2}{\sum_{k=1}^n(b_k-a_k)^2}\right), $$ provided the denominator is positive. In either form, applying the same bound to $-M_k$ gives a lower-tail bound; adding the two bounds gives a two-sided bound with prefactor $2$. If all increment bounds are zero, then $M_n-M_0=0$ almost surely and the probability is zero for $x>0$.

The absolute-bound form is a standard Azuma–Hoeffding result from the earlier material on conditional moment bounds. The range form uses the width $b_k-a_k$, not the largest absolute endpoint. Here is a short derivation of the range form to make that distinction explicit.

Proof. Fix $k$, and write $D=D_k$, $a=a_k$, and $b=b_k$. If $a=b$, then $D=a=b$ almost surely, and its conditional mean zero forces $D=0$ almost surely. Otherwise, convexity of $y\mapsto e^{\theta y}$ gives, for every real $\theta$ and $a\le y\le b$, $$ e^{\theta y}\le \frac{b-y}{b-a}e^{\theta a}+\frac{y-a}{b-a}e^{\theta b}. $$ Take conditional expectations given $\mathcal{F}_{k-1}$. Since $\mathbb{E}[D\mid\mathcal{F}_{k-1}]=0$, the resulting upper bound is the moment generating function of a mean-zero random variable supported on $\{a,b\}$, with probabilities $b/(b-a)$ and $-a/(b-a)$. These probabilities are nonnegative and sum to $1$, because a mean-zero variable in $[a,b]$ requires $a\le0\le b$.

For completeness, if $Y$ is any variable on the two endpoints with mean zero, set $K(\theta)=\log\mathbb{E}e^{\theta Y}$. Differentiation of this finite sum shows that $K(0)=K'(0)=0$ and that $K''(\theta)$ is the variance of a variable supported on $[a,b]$ under probabilities tilted by $e^{\theta Y}$. Any variable $Z\in[a,b]$ has variance at most $(b-a)^2/4$: since $(Z-a)(b-Z)\ge0$, taking expectations gives $\mathbb{E}Z^2\le(a+b)\mathbb{E}Z-ab$; subtracting $(\mathbb{E}Z)^2$ yields $\operatorname{Var}(Z)\le(\mathbb{E}Z-a)(b-\mathbb{E}Z)\le(b-a)^2/4$. Integrating the bound on $K''$ from $0$ to $\theta$, in either direction, gives $K(\theta)\le\theta^2(b-a)^2/8$. Consequently, $$ \mathbb{E}[e^{\theta D_k}\mid\mathcal{F}_{k-1}]\le e^{\theta^2(b_k-a_k)^2/8}. $$

Iterating conditional expectation gives $\mathbb{E}e^{\theta(M_n-M_0)}\le e^{\theta^2\sum_k(b_k-a_k)^2/8}$. For $\theta>0$, Markov's inequality bounds the upper-tail probability by this expression times $e^{-\theta x}$. If $V=\sum_k(b_k-a_k)^2>0$, choosing $\theta=4x/V$ gives $e^{-2x^2/V}$, as claimed. The zero-width case was handled above. $\square$

Absolute Bounds and Conditional Ranges

An absolute bound $|D_k|\le c_k$ places the increment in $[-c_k,c_k]$, an interval of width $2c_k$. Substitution into the range formula gives exponent $-2x^2/\sum_k(2c_k)^2=-x^2/(2\sum_k c_k^2)$, the absolute-bound version. Conversely, a conditional range $[a_k,b_k]$ can be used directly through its width. Because the conditional mean is zero, its endpoints must straddle zero, but the interval need not be centered at zero. Therefore its half-width need not bound the absolute increment.

Worked Example: Symmetric Increments and the Factor of Two

Let $\varepsilon_1,\ldots,\varepsilon_4$ be independent fair signs on a probability space, so each equals $1$ or $-1$ with probability $1/2$. Let $\mathcal{F}_k=\sigma(\varepsilon_1,\ldots,\varepsilon_k)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$, and set $M_k=\sum_{j=1}^k\varepsilon_j$, $M_0=0$. Independence and the equal sign probabilities give $\mathbb{E}[\varepsilon_k\mid\mathcal{F}_{k-1}]=0$, so this is a martingale and $D_k=\varepsilon_k$.

Each increment satisfies $|D_k|\le1$, and also lies in the range $[-1,1]$, whose width is $2$. For $x=2$, the absolute-bound formula has $\sum c_k^2=4$, hence exponent $-2^2/(2\cdot4)=-1/2$. The range formula has $\sum(b_k-a_k)^2=4\cdot2^2=16$, hence exponent $-2\cdot2^2/16=-1/2$. Both give the same valid upper bound $e^{-1/2}$.

Check: the exact probability is $\mathbb{P}(M_4\ge2)=5/16$: the sum is at least $2$ when there are $3$ or $4$ positive signs, giving $\binom43+\binom44=4+1=5$ outcomes among $2^4=16$. This is no larger than $e^{-1/2}$. In particular, using $c=1$ in the absolute-bound formula is correct; using the interval width $2$ as $c$ is also valid but weaker, giving exponent $-4/(2\cdot4\cdot4)=-1/8$.

Worked Example: An Asymmetric Conditional Range

Let $Y$ take value $-\tfrac14$ with probability $\tfrac34$, and value $\tfrac34$ with probability $\tfrac14$. On this probability space take the one-step filtration $\mathcal{F}_0=\{\varnothing,\Omega\}$, $\mathcal{F}_1=\sigma(Y)$, and define $M_0=0$, $M_1=Y$. Its conditional mean is zero because $$ \mathbb{E}[Y\mid\mathcal{F}_0]=-\tfrac14\cdot\tfrac34+\tfrac34\cdot\tfrac14=0. $$

The increment lies in $[-\tfrac14,\tfrac34]$, with width $1$, but its largest absolute value is $\tfrac34$. The range bound at $x=\tfrac12$ is $\exp(-2(\tfrac12)^2/1^2)=e^{-1/2}$. The absolute-bound formula can instead use $c=\tfrac34$, giving $\exp(-(\tfrac12)^2/(2(\tfrac34)^2))=e^{-2/9}$. The range bound is sharper here.

Check: $\mathbb{P}(M_1\ge\tfrac12)=\tfrac14$, since only the value $\tfrac34$ meets the inclusive threshold. Both stated upper bounds are consistent with this probability. Replacing the absolute bound $c=\tfrac34$ by half the range, $c=\tfrac12$, would fail the required assumption: the outcome $Y=\tfrac34$ has positive probability and exceeds $\tfrac12$. The range formula, not that false absolute-bound premise, justifies the sharper result.

Check the Filtration and the Type of Bound

A statement such as “the increments are centered” must mean centered conditionally on the information available just before each increment. An unconditional equality $\mathbb{E}D_k=0$ is not enough. Likewise, a bound on a conditional variance or on an expected absolute value is not an almost-sure bound on the increment. The next examples isolate these two errors.

Worked Example: A Variance Bound Is Not a Bounded-Increment Bound

On a probability space, let $D$ equal $3$ with probability $\tfrac1{18}$, equal $-3$ with probability $\tfrac1{18}$, and equal $0$ with probability $\tfrac89$. Take $\mathcal{F}_0$ trivial and $\mathcal{F}_1=\sigma(D)$, and set $M_0=0$, $M_1=D$. Direct calculation gives $\mathbb{E}[D\mid\mathcal{F}_0]=3/18-3/18=0$ and $\operatorname{Var}(D\mid\mathcal{F}_0)=9/18+9/18=1$.

The variance is $1$, but $|D|\le1$ is false: $|D|=3$ with probability $1/9$. If one incorrectly substitutes $c=1$ into the absolute-bound formula at $x=3$, the claimed bound is $e^{-9/2}$. The actual upper-tail probability is $\mathbb{P}(D\ge3)=1/18$, which is greater than $e^{-9/2}$. Indeed, the positive-term expansion gives $e^{9/2}>1+\tfrac92+\tfrac{(9/2)^2}{2}+\tfrac{(9/2)^3}{6}>18$, so $e^{-9/2}<1/18$.

Correction: the martingale-difference condition holds, but the bounded-increment hypothesis does not. A variance bound alone does not authorize this Azuma–Hoeffding application; a different concentration result would require its own hypotheses and proof.

Worked Example: Conditioning on the Wrong Information

Let $\Omega$ contain one outcome, let $\mathcal{F}_0=\mathcal{F}_1=\{\varnothing,\Omega\}$, and set $M_0=0$, $M_1=1$. This process is adapted, and its increment satisfies $|D_1|=1$, but $\mathbb{E}[D_1\mid\mathcal{F}_0]=1$, not $0$. Thus it is not a martingale.

If the conditional-mean check is omitted, the absolute-bound formula with $c_1=1$ and $x=1$ would assert $\mathbb{P}(M_1-M_0\ge1)\le e^{-1/2}$. The left side is $1$, so the assertion is false. The failure is exactly the missing martingale condition, not a problem with the increment bound.

A filtration error can also arise by including information about an increment too early. If $Y$ is a fair sign, $M_0=0$, $M_1=Y$, and one sets $\mathcal{F}_0=\sigma(Y)$, then $\mathbb{E}[M_1-M_0\mid\mathcal{F}_0]=Y$, which is not zero almost surely. To use a martingale bound, verify the conditional expectation relative to the stated $\mathcal{F}_{k-1}$, not merely relative to a smaller or larger information set chosen after the calculation.

A Practical Diagnostic

Before applying an Azuma–Hoeffding bound, write down the filtration and the increments explicitly. Then check the conditions in order:

Adaptation and integrability: $M_k$ is $\mathcal{F}_k$-measurable and integrable.
Conditional centering: $\mathbb{E}[D_k\mid\mathcal{F}_{k-1}]=0$ almost surely for every step.
Correct bound: establish either $|D_k|\le c_k$ almost surely or an interval $a_k\le D_k\le b_k$ almost surely. Do not replace an almost-sure statement with a variance or expectation bound.
Correct constants: use $c_k$ in the denominator $2\sum c_k^2$, or use the full range width $b_k-a_k$ in the denominator $\sum(b_k-a_k)^2/2$.
Tail event: distinguish $\{M_n-M_0\ge x\}$ from a two-sided event; the latter requires adding the lower-tail probability.

The most frequent factor error is to use half the range width as an absolute bound. For increments in $[-1,1]$, the absolute bound is $1$, while the range width is $2$. The half-width happens to equal the absolute bound because this interval is centered at zero. In an asymmetric interval such as $[-\tfrac14,\tfrac34]$, its half-width is $\tfrac12$, which does not bound the absolute increment. The range theorem remains available, but the absolute-bound theorem cannot be invoked with that false constant.

Check Your Understanding

For each proposed bound, identify the relevant assumption before choosing its constants.

If $D_k\in[-2,1]$ almost surely and has conditional mean zero, what range width enters the range form? What absolute bound can be used directly?
For $n$ martingale differences with $|D_k|\le3$, write the one-sided Azuma–Hoeffding exponent at threshold $x>0$.
Why does $\mathbb{E}[D_k]=0$ not by itself establish the martingale-difference condition relative to $\mathcal{F}_{k-1}$?
A conditional variance is at most $4$, but no almost-sure increment bound is known. Which assumption needed for the absolute-bound form is missing?
For a two-sided deviation event, why is a factor of $2$ added to the one-sided bound?