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

The moment-generating function is $M_X(t)=\mathbb{E}[e^{tX}]$ on the set where this expectation is finite. For independent, identically distributed summands, independence factors the expectation:The identity holds wherever the factors are finite; in the remaining parts the bounded summands make them finite for every real $t$.

Chebyshev's inequality states $\mathbb{P}(|Y-\mu |\ge r)\le {\sigma }^2/r^2$ for $r>0$ when $Y$ has mean $\mu$ and finite variance ${\sigma }^2$. Here each summand has mean zero and variance one, so independence gives $\mathbb{E}{S}_n=0$ and $\mathrm{Var}{S}_n=n$. Taking $r=an$ gives

The two-point distribution gives $M(t)=(e^t+e^{-t})/2=\cosh t$. In the power series, $(2j)!={\prod }_{r=1}^j(2r)(2r-1)\ge 2^{j}j!$, so each coefficient satisfiesSumming the nonnegative terms proves $\boxed{M(t)\le e^{t^2/2}}$ for every real $t$. Part (a) therefore givesThis is the sub-Gaussian moment bound for a symmetric random sign.

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$.