0
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Is there a research angle to this problem? If not, it's off-topic on this website, as per the faq. $\endgroup$ Nov 23 '12 at 4:26
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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