Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

Your Answer


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.