= Solution
Let
$$
\tau=\min\bigl(\{m\leq n:|S_m|>x\}\cup\{n\}\bigr).
$$
Because $|X_m|\leq K$, one always has $|S_\tau|\leq x+K$: this is clear if no crossing occurs, and at the first crossing the overshoot is at most one increment. Apply the <optional stopping theorem> to the martingale from part (c):
$$
\mathbb E[S_\tau^2]=\mathbb E[V_\tau]\leq(x+K)^2.
$$
On the event $\{\max_{m\leq n}|S_m|\leq x\}$ one has $\tau=n$, so $V_\tau=V_n$. Since $V_\tau\geq0$ everywhere,
$$
V_n\mathbb P\left(\max_{m\leq n}|S_m|\leq x\right)
\leq\mathbb E[V_\tau]
\leq(x+K)^2.
$$
Hence
$$
\boxed{\mathbb P\left(\max_{1\leq m\leq n}|S_m|\leq x\right)
\leq\frac{(x+K)^2}{\operatorname{Var}(S_n)}.}
$$
Back to article page
