SCHWEITZER 2005 Problem 12

Let $x_1,x_2,\cdots,x_n$ be iid rv. $S_n=\sum x_k$ (a) let $P(|x_1|\leq 1)=1$ , $E[x_1]=0$ , $E[x_1^2]=\sigma^2>0$ Prove that $\exists C>0$ , $\forall u\geq 2n\sigma^2$ $P(S_n\geq u)\leq e^{-C u \log(u/n\sigma^2)}$ (b) let $P(x_1=1)=P(x_1=-1)=\sigma^2/2$ , $P(x_1=0)=1-\sigma^2$ Prove that $\exists B_1<1,B_2>1,B_3>0$ , $\forall u\geq1, B_1 n\geq u\geq B_2 n\sigma^2$ $P(S_n\geq u)>e^{-B_3 u \log(u/n\sigma^2)}$