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
-
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$– usulApr 1, 2015 at 14:38
-
$\begingroup$ This is what Chernoff bounds are for. See e.g. wikipedia and stackexchange. $\endgroup$– Neal YoungApr 1, 2015 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řábekApr 1, 2015 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$– usulApr 2, 2015 at 0:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
answered Apr 1, 2015 at 18:03
-
$\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$– RamApr 3, 2015 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$ Apr 3, 2015 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$– RamApr 27, 2015 at 7:20