Upper and lower bound of binomial summation

For $n>1$ and $~0<p \leq 1$, can we upper and lower bound the following binomial series in terms of $n$ and $p$ $$\Sigma_{i=\lceil p n \rceil}^n {n \choose i} (p )^i(1-p)^{(n-i)}$$

• You want the probability that the number of coin flips exceeds its mean? Of course this will be very close to $0.5$ in "normal" regimes. Otherwise, what if $pn$ is not an integer?
– usul
Apr 1 '15 at 14:38
• This is what Chernoff bounds are for. See e.g. wikipedia and stackexchange. Apr 1 '15 at 16:03
• This is not what Chernoff bounds are for. Chernoff bounds are applicable to tails bounded away from the expected value. Here, they only give the useless result that the sum is at most $1$. Apr 1 '15 at 17:23
• I believe it is known that the median of the binomial is always either $\lfloor pn \rfloor$ or $\lceil pn \rceil$. If that's correct, then you can upper-bound the distance of this quantity from $\frac{1}{2}$ by something like the probability that you get exactly the median number of coin flips. In general if $np < 1$ or $np > n-1$ then you just need to compute the probability of the extreme case (all tails or all heads respectively).
– usul
Apr 2 '15 at 0:01

Let me denote the sum as $S_{n,p}$. It gives the probability that a random sample from the binomial distribution $B(n,p)$ exceeds its expected value.

For $0<p<1$ constant, the central limit theorem tells you that $B(n,p)$ looks like the normal distribution $N(pn,p(1-p)n)$ for large $n$. Since this is symmetric, $S_{n,p}$ will be approximately $1/2$ as noted in usul’s comment.

This can be quantified using the Berry–Esseen theorem: applying it to $n$ indicator random variables with mean $p$, variance $p(1-p)$, and third moment $(p^2+(1-p)^2)p(1-p)\le p(1-p)$, gives

$$\left|S_{n,p}-\tfrac12\right|\le\frac C{\sqrt{p(1-p)n}}$$

for a certain constant $C<1/2$.

• Dear Prof. Jeřábek, Thanks for the response. I have a basic doubt regarding the answer: #The formula quoted in Berry–Esseen theorem require the first moment to be zero. But in our case we have E[X_i] = p. So it is not clear to me how the formula can be directly applied here. Pls let me know if I am making any fundamental mistake in understanding this. Thanks in advance. -Best Ram
– Ram
Apr 3 '15 at 4:41
• To use the formula on the Wikipedia page, you need to normalize the distribution to have expectation 0. That is, the $X_i$ you apply it to has value $1-p$ with probability $p$, and $-p$ with probability $1-p$. For the same reason, you evaluate the formula at $x=0$. Apr 3 '15 at 10:03
• Thanks for your response. Is the better lower bound known for the above, ie. tighter bound for $S_{n,p} \geq 0.5-\frac C{\sqrt{p(1-p)n}}$.
– Ram
Apr 27 '15 at 7:20