Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

1 Answer

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 http://www.jstor.org/discover/10.2307/2236142?uid=2129&uid=2&uid=70&uid=4&sid=21101337407023

share|improve this answer
add comment

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.