Exponential Martingale Maximal Tail Bound

Setup

For a simple random walk $(X_t)$ and the exponential martingale

$$ M_t(\theta)=\exp(\theta X_t-t\lambda(\theta)), $$

Doob’s maximal inequality gives a tail bound for the running maximum of $X_t$.

If $X_t\ge b$ for some $t\le n$, then

$$ M_t(\theta)\ge e^{\theta b-n\lambda(\theta)}. $$

$$ \left\{\max_{0\le t\le n}X_t\ge b\right\} \subseteq \left\{\max_{0\le t\le n}M_t(\theta)\ge e^{\theta b-n\lambda(\theta)}\right\}. $$

Since $(M_t(\theta))$ is a nonnegative martingale,

$$ \mathbb P\left(\max_{0\le t\le n}X_t\ge b\right) \le e^{-\theta b+n\lambda(\theta)}. $$

For the simple random walk,

$$ \lambda(\theta)\le \frac{\theta^2}{2}, $$

$$ \mathbb P\left(\max_{0\le t\le n}X_t\ge b\right) \le e^{-\theta b+n\theta^2/2}. $$

Optimizing at $\theta=b/n$ yields

$$ \mathbb P\left(\max_{0\le t\le n}X_t\ge b\right) \le e^{-b^2/(2n)}. $$