Why Control the Whole Path?
A martingale can cross a high boundary and then return below it before the final time. A concentration bound for its value at one fixed time therefore does not, by itself, control the probability of crossing the boundary at any earlier time. A maximal Azuma bound addresses the path event directly: it uses an exponential supermartingale and stops it at the first crossing.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) with a discrete-time filtration \((\mathcal{F}_k)_{k=0}^{N}\). Let \((M_k)_{k=0}^{N}\) be an adapted, integrable, real-valued process, so its state space is \(\mathbb{R}\). It is a martingale if \(\mathbb{E}[M_k\mid\mathcal{F}_{k-1}]=M_{k-1}\) almost surely for every \(1\le k\le N\). Write \(D_k=M_k-M_{k-1}\) for its increments. Assume there are deterministic constants \(c_k\ge0\) such that \(|D_k|\le c_k\) almost surely. The boundary \(a\) below is strictly positive, and the crossing event includes equality: \(\max_{0\le k\le N}(M_k-M_0)\ge a\).
Proof. If \(c=0\), then \(D=0\) almost surely and both sides equal \(1\). Suppose \(c>0\). For every \(x\in[-c,c]\), convexity of \(x\mapsto e^{\theta x}\) gives the chord bound \(e^{\theta x}\le \frac{c+x}{2c}e^{\theta c}+\frac{c-x}{2c}e^{-\theta c}\). Substitute \(D\) and take conditional expectations given \(\mathcal{G}\). Using \(\mathbb{E}[D\mid\mathcal{G}]=0\), the result is at most \(\frac12(e^{\theta c}+e^{-\theta c})=\cosh(\theta c)\). Finally, \(\cosh y\le e^{y^2/2}\): term by term, \(\cosh y=\sum_{r\ge0}y^{2r}/(2r)!\), and \((2r)!\ge 2^r r!\), so this series is at most \(\sum_{r\ge0}(y^2/2)^r/r!=e^{y^2/2}\). This proves the bound. \(\square\)
The Maximal Azuma Bound
Proof. First suppose \(C_N>0\), and fix \(\theta>0\). Define \(V_0=0\), \(V_k=\sum_{i=1}^{k}c_i^2\), and \(Z_k=\exp\!\left(\theta(M_k-M_0)-\frac{\theta^2}{2}V_k\right)\). This process is adapted, positive, and \(Z_0=1\). Since \(D_k\) has conditional mean zero given \(\mathcal{F}_{k-1}\) and \(|D_k|\le c_k\), the lemma gives \(\mathbb{E}[Z_k\mid\mathcal{F}_{k-1}]=Z_{k-1}e^{-\theta^2c_k^2/2}\mathbb{E}[e^{\theta D_k}\mid\mathcal{F}_{k-1}]\le Z_{k-1}\). Thus \((Z_k)\) is a nonnegative supermartingale.
Let \(\tau\) be the first \(k\in\{0,\ldots,N\}\) for which \(M_k-M_0\ge a\), and set \(\tau=N\) if there is no such \(k\). This is a bounded stopping time: for each \(k<N\), the event \(\{\tau\le k\}\) is determined by \(M_0,\ldots,M_k\), and hence belongs to \(\mathcal{F}_k\). The stopped process satisfies \(\mathbb{E}[Z_{k\wedge\tau}]\le\mathbb{E}[Z_{(k-1)\wedge\tau}]\) for \(1\le k\le N\). Indeed, on \(\{\tau\le k-1\}\) it does not change, while on \(\{\tau>k-1\}\) the conditional supermartingale inequality applies. Iterating these finite inequalities yields \(\mathbb{E}[Z_\tau]\le Z_0=1\).
On the crossing event \(A=\{\max_{0\le k\le N}(M_k-M_0)\ge a\}\), the stopping time is an actual crossing time, so \(M_\tau-M_0\ge a\). Also \(V_\tau\le C_N\). Consequently \(Z_\tau\ge \exp(\theta a-\theta^2C_N/2)\) on \(A\); positivity gives \(1\ge\mathbb{E}[Z_\tau]\ge\mathbb{P}(A)\exp(\theta a-\theta^2C_N/2)\). Rearranging proves \(\mathbb{P}(A)\le\exp(-\theta a+\theta^2C_N/2)\). The exponent is minimized over \(\theta>0\) at \(\theta=a/C_N\): its derivative is \(-a+\theta C_N\), which vanishes there, and its second derivative is \(C_N>0\). Substitution gives the stated bound. If \(C_N=0\), every \(c_k=0\), so every increment is zero almost surely. Thus \(M_k=M_0\) at all the finitely many times, and a positive boundary cannot be crossed. \(\square\)
The result controls the maximum of the entire path using the total squared increment bounds \(C_N\). It does not require the increments to be independent: the conditional mean-zero and boundedness assumptions are enough. If the bounds vary with time, each \(c_k^2\) contributes separately to the exponent.
Worked Example: A Four-Step Symmetric Random Walk
Let \(\Omega=\{-1,1\}^4\) have the uniform probability measure, let \(\mathcal{F}_k\) record the first \(k\) coordinates, and let \(M_0=0\), \(M_k=\sum_{i=1}^k D_i\), where the coordinates \(D_i\) are independent and take each of \(-1,1\) with probability \(\tfrac12\). The state space is \(\mathbb{R}\) and the time indices are \(0,\ldots,4\). Each increment has conditional mean \(\tfrac12(1)+\tfrac12(-1)=0\), and \(|D_i|\le1\), so \(c_i=1\) for all four steps. Therefore \(C_4=1^2+1^2+1^2+1^2=4\).
For the boundary \(a=\tfrac52\), the theorem gives \(\mathbb{P}(\max_{0\le k\le4}M_k\ge\tfrac52)\le \exp(-(\tfrac52)^2/(2\cdot4))=e^{-25/32}\). The optimized parameter is \(\theta=a/C_4=(\tfrac52)/4=\tfrac58\). Substituting it into \(-\theta a+\theta^2C_4/2\) gives \(-\tfrac58\cdot\tfrac52+(\tfrac58)^2\cdot4/2=-\tfrac{25}{16}+\tfrac{25}{32}=-\tfrac{25}{32}\).
Check by counting paths: Since the walk changes by one at each step, crossing \(\tfrac52\) means reaching \(3\). A crossing by step \(3\) requires the first three increments all to be \(1\), which allows \(2\) choices for the fourth increment. A first crossing at step \(4\) requires the first three increments to contain exactly two \(1\)'s and one \(-1\), followed by a \(1\); there are \(3\) such paths. The two cases are disjoint, so the probability is \((2+3)/16=5/16\). This exact path count illustrates the event being bounded; the exponential bound is an upper estimate, not an exact probability.
Worked Example: Unequal Increment Bounds
Let \(\Omega=\{-1,1\}^3\) be uniform, with its coordinate filtration, and let the independent increments be \(D_1=\varepsilon_1\), \(D_2=2\varepsilon_2\), and \(D_3=\varepsilon_3\), where each coordinate \(\varepsilon_i\) takes \(-1\) and \(1\) with probability \(\tfrac12\). Define \(M_0=0\) and \(M_k=\sum_{i=1}^kD_i\); the state space is \(\mathbb{R}\). Each conditional increment mean is zero, and the bounds are \(c_1=1,c_2=2,c_3=1\). Thus \(C_3=1^2+2^2+1^2=6\).
At boundary \(a=3\), the maximal bound is \(\exp(-3^2/(2\cdot6))=e^{-3/4}\), with optimizing parameter \(\theta=3/6=\tfrac12\). Directly, a path crosses \(3\) if and only if its first increment is \(1\) and its second increment is \(2\). Those two increments reach \(3\) at time \(2\), regardless of the third; no other first-two-increment combination reaches \(3\), and the third increment alone cannot raise any other combination to \(3\). There are \(2\) such paths among \(8\), so the crossing probability is \(2/8=1/4\).
Check: The exponent from the optimized expression is \(-\theta a+\theta^2C_3/2=-(\tfrac12)(3)+(\tfrac12)^2(6)/2=-\tfrac32+\tfrac34=-\tfrac34\), as claimed. The sum \(6\) uses the squared bounds, not the sum \(1+2+1\).
Worked Example: Asymmetric Mean-Zero Increments
Let \(\Omega=\{1,-\tfrac12\}^2\), where each coordinate independently equals \(1\) with probability \(\tfrac13\) and \(-\tfrac12\) with probability \(\tfrac23\). Use the coordinate filtration, set \(M_0=0\), and let \(M_k\) be the sum of the first \(k\) coordinates. This is a real-valued process at times \(0,1,2\). For either increment, the mean is \(\tfrac13(1)+\tfrac23(-\tfrac12)=0\); the absolute increment is at most \(1\). Hence \(c_1=c_2=1\) and \(C_2=2\).
For \(a=\tfrac32\), the bound is \(\exp(-(\tfrac32)^2/(2\cdot2))=e^{-9/16}\), and the optimizing parameter is \(\theta=(\tfrac32)/2=\tfrac34\). The path can reach \(\tfrac32\) only if both increments equal \(1\): one increment alone is at most \(1\), and if either increment equals \(-\tfrac12\), the sum of both is at most \(\tfrac12\). The probability of two increments equal to \(1\) is \(\tfrac13\cdot\tfrac13=\tfrac19\).
Check: Substitution gives \(-\theta a+\theta^2C_2/2=-(\tfrac34)(\tfrac32)+(\tfrac34)^2(2)/2=-\tfrac98+\tfrac9{16}=-\tfrac9{16}\). The conditional mean calculation verifies the martingale assumption even though the increments are not symmetric.
Why Stopping at the Crossing Matters
A common mistake is to use a terminal-time tail bound as though it controlled the maximum. For example, for a two-step symmetric random walk with increments independently equal to \(-1\) or \(1\) with probability \(\tfrac12\), the event \(\max_{0\le k\le2}M_k\ge1\) has probability \(3/4\): it occurs whenever the first increment is \(1\), or when the first is \(-1\) and the second is \(1\). But \(M_2\ge1\) occurs only when both increments are \(1\), with probability \(1/4\). Thus the terminal event misses paths that cross and then fall back. The correction is to stop the exponential supermartingale at the first crossing, as in the proof, rather than replace the maximum event by a terminal event.
The bound is useful whenever a process is revealed step by step and each new increment is conditionally centered and bounded. It can control the chance that a deviation becomes large at any stage, not merely at the end. The assumptions matter: without conditional mean zero, the exponential process need not be a supermartingale; without bounded increments (or another suitable conditional exponential-moment bound), the lemma used in the proof need not hold. The inequality is an upper bound and may be conservative, as the exact path counts in the examples demonstrate.
Check Your Understanding
Use the hypotheses and proof above to work through these questions.
- For a martingale with \(N=5\) and \(c_k=2\) at every step, calculate \(C_N\) and state the maximal bound at a positive boundary \(a\).
- Why does the conditional exponential bound still apply when an increment is not symmetrically distributed?
- For \(c_1=1,c_2=0,c_3=2\), calculate \(C_3\) and the parameter that optimizes the exponent for a boundary \(a>0\).
- What does the maximal bound say when all increment bounds are zero and the boundary is strictly positive?
- Give a path-based explanation of why a terminal-time concentration bound does not automatically bound the probability of crossing earlier.