= Solution
Put $V=\operatorname{Var}(S_n)=\sum_{m=1}^nv_m$. If $\max_{m\leq n}S_m\geq x$, then
$$
\max_{m\leq n}(S_m+c)^2\geq(x+c)^2.
$$
The <Doob maximal inequality for a nonnegative submartingale> therefore gives
$$
\mathbb P\left(\max_{m\leq n}S_m\geq x\right)
\leq\frac{\mathbb E[(S_n+c)^2]}{(x+c)^2}
=\frac{V+c^2}{(x+c)^2}.
$$
The right side is minimized at $c=V/x$, and substitution gives
$$
\boxed{\mathbb P\left(\max_{1\leq m\leq n}S_m\geq x\right)
\leq\frac{\operatorname{Var}(S_n)}
{\operatorname{Var}(S_n)+x^2}.}
$$
Back to article page
