MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

I know this is an easy problem, but I can't figure it out.

A particle takes discrete steps $σ_1,σ_2,σ_3,…,σ_n$ which take on values +1 or −1. However, $P(σ_i=+1)=p$ and $P(σ_i=−1)$ will be $1-p$.

So I am interested in bound of $ P (\sum_{i}{\sigma_i} \geq k)$ ?

I tried to use Chernoff's bound, but it doesnt give me a good bound. Also for Chernoff I need to have $k \geq \mu$.

Can I say that $\sigma$-s correspond to some other $Y_i$, such that $Y_i = 1$, with prob. $p$ and $0$, with prob $1-p$, and we are interested in

$P(\sum_i{Y_i} \geq k/2)$?

share|cite|improve this question
Is there a research angle to this problem? If not, it's off-topic on this website, as per the faq. – Gerry Myerson Nov 23 '12 at 4:26

Assuming the $\sigma_i$ (and thus $Y_i$) are independent, the distribution of $S_n = \sum_{i=1}^n Y_i$ is binomial with parameters $n$ and $p$. If the Chernoff and Chebyshev inequalities are not good enough for your purposes, you might try a more quantitative version of the DeMoivre-Laplace theorem: see W. Feller, "On the normal approximation to the binomial distribution", Annals of Mathematical Statistics 16 (1945) 319-329

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.