Exponential maximal bound for a symmetric random walk
= Exponential maximal bound for a symmetric random walk
{title2=$\mathbb P(\max_{k\le n}S_k\ge t\sqrt n)\le e^{-t^2/2}$}
For a <simple symmetric random walk>, the estimate $\mathbb E e^{\theta S_n}\le e^{n\theta^2/2}$ and the exponential maximal inequality give $\mathbb P(\max_{k\le n}S_k\ge t\sqrt n)\le e^{-t^2/2}$ for $t\ge0$.