# Simple markov chain problem

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

• Is there a research angle to this problem? If not, it's off-topic on this website, as per the faq. 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 http://www.jstor.org/discover/10.2307/2236142?uid=2129&uid=2&uid=70&uid=4&sid=21101337407023