Doob Random-Walk Maximal Bound

Doob's Inequalities

Let S_k be a random walk starting at S_0 = 0 with independent ± 1 steps. The sequence S_k^2 is a submartingale. By Doob's maximal inequality, for any finite horizon n and threshold a > 0:

P(\max_(0 ≤ k ≤ n) |S_k| ≥ a) ≤ min(1, n/(a²))

Furthermore, Doob's L2 inequality bounds the expected maximum square by a multiple of the final expected square:

E[\max_(0 ≤ k ≤ n) S_k²] ≤ 4 E[S_n²] = 4n

Unlike the fixed-time Chebyshev bound, which only considers S_n, this bound uniformly applies to the entire path up to step n, accounting for paths that may cross the threshold and return to zero.

Path Enumeration at n = 4

Consider a 4-step random walk. There are 2^4 = 16 possible paths. Let us compute the exact probability of ever reaching |S_k| ≥ 2 versus the probability of ending at |S_4| ≥ 2, along with expectations to verify Doob's L2 bound.

1. Count the paths: Of the 16 total paths, 12 paths reach an absolute value of 2 or more at some point during the 4 steps.
2. Ever crossing probability: The exact chance is 12 / 16 = 0.75.
3. Terminal crossing probability: Only 10 paths end exactly at ± 2 or ± 4. Thus, P(|S_4| ≥ 2) = 10 / 16 = 0.625.
4. Doob tail bound: By the inequality, P(max |S_k| ≥ 2) ≤ 4 / 2² = 1.0. Here, 0.75 ≤ 1.0 holds.
5. Expected terminal square: Each step has variance 1, so E[S_4^2] = 4. The Doob L2 bound predicts the max square is at most 4 × 4 = 16.
6. Expected maximum square: Computing over all 16 paths yields an exact E[max S_k²] = 5.375, comfortably below the bound of 16.

Exploring Random Walks

Use the interactive controls to visualize and verify Doob's bounds for different path lengths and thresholds.

1. Set the steps parameter to explore longer horizons.
2. Adjust the threshold to see how the tail bound becomes sharper or trivial (1.0).
3. Observe the difference between the "Ever crossing" probability and the "Terminal crossing" probability.
4. Note how the expected maximum square remains strictly bounded by 4 times the expected terminal square.

Limitations

The simple bounds presented here are loose for large thresholds and assume independent, bounded symmetric increments. They do not directly apply to processes with drift or heavy-tailed step distributions without modification. The brute-force path enumeration used in this module is exponentially complex O(2^n) and only feasible for small horizons.

References

Doob, J. L. (1953). Stochastic Processes. Wiley. This classic text formally establishes martingale theory, including the maximal and L2 bounds. It details how the maximal value of a submartingale relates to its final expectation, providing the foundational results discussed in this module. The accompanying maximal inequality notes provide additional contemporary explanations and derivations useful for modern study.
Doob's Maximal Inequality Notes