Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.