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

  • 4
    $\begingroup$ 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? $\endgroup$ – usul Apr 1 '15 at 14:38
  • $\begingroup$ This is what Chernoff bounds are for. See e.g. wikipedia and stackexchange. $\endgroup$ – Neal Young Apr 1 '15 at 16:03
  • 4
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Apr 1 '15 at 17:23
  • 1
    $\begingroup$ 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). $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Ram Apr 3 '15 at 4:41
  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Apr 3 '15 at 10:03
  • $\begingroup$ 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}}$. $\endgroup$ – Ram Apr 27 '15 at 7:20

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.