Past exam of the options II course of the University of Oxford / 2013 / M5 / b / iii

For $t>0$, apply Markov's inequality to the nonnegative random variable $e^{t{S}_n}$. The exponential is then increasing, soAt $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\ge an)\le e^{-n{a}^2/2}$. The distribution is symmetric, so the same bound holds for $S_n\le -an$. A union bound givesOne may also cap this at one. Its exponential decay is stronger than the polynomial Chebyshev bound for fixed $a>0$ and large $n$.