<p>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.</p>

<p>For $0&lt;p&lt;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.</p>

<p>This can be quantified using the <a href="http://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem">Berry–Esseen theorem</a>: 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</p>

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

<p>for a certain constant $C&lt;1/2$.</p>

CC BY-SA 3.0
2015-04-03T04:41:59.170Z
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
CC BY-SA 3.0
2015-04-03T10:03:47.723Z
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$.
Emil Jeřábek
CC BY-SA 3.0
2015-04-27T07:20:34.607Z
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
CC BY-SA 3.0
2015-04-01T18:03:09.707Z
2015-04-01T18:03:09.707Z
Emil Jeřábek
<p>For $n&gt;1$ and $~0&lt;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)}$$</p>

CC BY-SA 3.0
2015-04-01T14:38:09.467Z
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
CC BY-SA 3.0
2015-04-01T16:03:15.513Z
This is what Chernoff bounds are for.  See e.g. [wikipedia](http://en.wikipedia.org/wiki/Chernoff_bound#Theorem_for_multiplicative_form_of_Chernoff_bound_.28relative_error.29) and [stackexchange](http://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound).
Neal Young
CC BY-SA 3.0
2015-04-01T17:23:04.613Z
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$.
Emil Jeřábek
CC BY-SA 3.0
2015-04-02T00:01:20.840Z
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
<pr.probability>
Upper and lower bound of binomial summation
Ram
# Upper and lower bound of binomial summation

(Asked by: username_0 on 2015-04-01)

For $n>1$ and $~0

**Tags:** pr.probability

> **Comments:**
> **username_1**: 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?  
> **username_2**: This is what Chernoff bounds are for.  See e.g. [wikipedia](http://en.wikipedia.org/wiki/Chernoff_bound#Theorem_for_multiplicative_form_of_Chernoff_bound_.28relative_error.29) and [stackexchange](http://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound).  
> **username_3**: 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$.  
> **username_1**: 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).  

---

## 1 answers

### Answer by username_3 on 2015-04-01. Score: 9 | Accepted answer

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

This can be quantified using the [Berry–Esseen theorem](http://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_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$.

> **Comments:**
> **username_0**: 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    username_0  
> **username_3**: 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$.  
> **username_0**: 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}}$.  

---

