= Solution
For $t>0$, apply <Markov's inequality> to the nonnegative random variable $e^{tS_n}$. The exponential is then increasing, so
$$
\mathbb P(S_n\geq an)\leq e^{-tan}\mathbb E[e^{tS_n}]
\leq\exp\left[n\left(\frac{t^2}{2}-at\right)\right].
$$
At $t=0$ the right side is one. For $t<0$ it exceeds one because $a>0$, so the same displayed bound remains true trivially; the upper-tail Markov argument itself uses $t>0$.
Complete the square $t^2/2-at=(t-a)^2/2-a^2/2$. Choosing $t=a$ gives the strongest bound from this family, $\mathbb P(S_n\geq an)\leq e^{-na^2/2}$. The distribution is symmetric, so the same bound holds for $S_n\leq-an$. A union bound gives
$$
\boxed{\mathbb P(|S_n|\geq an)\leq2e^{-na^2/2}.}
$$
One may also cap this at one. Its exponential decay is stronger than the <polynomial> Chebyshev bound for fixed $a>0$ and large $n$.
Back to article page
