# Random walk, using Chernoff…

Question: Let $S_n$ be the position of a person in a random walk on the n'th step (with equal probabilities for left and right), $S_0=0$ Prove (using Chernoff) that : $P(|Sn| \ge t)\le 2e^{\frac {t^2}{2n}}$

We learned this Chernoff bound: $P(X> \frac n2+t)\le e^{\frac {-2t^2}n}$

What I did:

I marked $R_n\sim Bin(n, \frac 12)$ as an RV counting the steps to the right, and $L_n=n-R_n$ as the left steps counter. So $S_n=2R_n -n$ Putting this in the inequality, doesn't give the wanted result...

-

Here is Chernoff's method : for all $\theta > 0$, Markov's inequality yields $$P(S_n \geq t) = P(e^{\theta S_n} \geq e^{\theta t}) \leq e^{-\theta t}E(e^{\theta S_n})$$ Now, you have to compute $E(e^{\theta S_n})$ and choose $\theta > 0$ such that the l.h.s. is the smallest possible.
After this, check that $P(|S_n| \geq t) = P(S_n \geq t) + P(S_n \leq -t) = 2P(S_n \geq t)$.