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

Improve this question
$\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$
    – Gerry Myerson
    Commented Nov 23, 2012 at 4:26

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .