# Asymptotics of sum of Binomial Coefficients (Binomial distribution) - Poisson approximation?

Let $$f(n):=\sum_{i=k}^n {n \choose i } p^i (1-p)^{n-i}$$ where $k\geq 2$ is a fixed Parameter and $p=p(n) \in (0,1]$ depends on $n$ where $np\leq 1$. We consider $n \rightarrow \infty$.

I've found the following Derivation of an asymptotic Approximation of $f$, but I have no idea how to get to this:

$$f(n)={n \choose k} p^k (1+O(np))=\frac{(np)^k}{k!}(1+O(np+n^{-1}))$$

A hint might be that one can approximate the binomial coefficient by the poisson probability $$\hat{f}(n)=\sum_{i=k}^{\infty} \frac{(np)^i}{i!}e^{-np}$$ where $|f(n)-\hat{f}(n)|<p$ and $\hat{f}(n)$ is asymptotically distributed like $\frac{(np)^k}{k!}$. If this Approximation is used, then I'd also like to know how one get to this asymptotic behavior $\frac{(np)^k}{k!}$ of the poisson.

A further hint might be on this site where it is written that $${n \choose i}p^i (1-p)^{n-i}= \frac{(np)^i e^{-np}}{i!}+o(1)$$ but even with this I am stuck.

I'm really stuck with each of the equations, I can't derive any of them. So I would really appreciate any hint.

• If $k$ and $p$ are fixed and $np \le 1$, there is nothing left to go to $\infty$. How can you talk about asymptotics? – Robert Israel Apr 24 '14 at 7:42
• Ok I see. Thank you for pointing that out. Let $k$ be fixed, and let $p=p(n)$ depend on $n$, but such that $p(n)n\leq 1$. it would be even better, if we don't Need the assumption that $p(n) n \leq 1$ but I think one Needs that to prove the above Statement. I've edited the original post. – user136457 Apr 24 '14 at 7:45

For every Bernoulli random variable $X$ with parameter $p$ there exists some Poisson random variable $Y$ with parameter $p$ such that $$P(X\ne Y)\leqslant p(1-\mathrm e^{-p})\leqslant p^2.$$ Thus, for every binomial random variable $S$ with parameter $(n,p)$ there exists some Poisson random variable $Z$ with parameter $np$ such that $$P(S\ne Z)\leqslant np^2.$$ In particular, for every $k$, $f(n)=P(S\geqslant k)$ and $\hat f(n)=P(Z\geqslant k)$ are such that $|f(n)-\hat f(n)|\leqslant np^2$.

Furthermore, $\hat f(n)=\dfrac{(np)^k}{k!}g(n)$ where $$g(n)=\mathrm e^{-np}\sum_{i\geqslant k}(np)^{i-k}\frac{k!}{(k+i)!},$$ hence $$\mathrm e^{-np}\leqslant g(n)\leqslant\sum_{i\geqslant k}(np)^{i-k}=\frac1{1-np}.$$ These bounds are nonasymptotic and valid for every $(n,p,k)$ such that $np\lt1$. Do these imply the asymptotics you are interested in?

For the approximation result mentioned in this answer, see R. J. Serfling, Some Elementary Results on Poisson Approximation in a Sequence of Bernoulli Trials (1976), freely available as preprint M374 on this Tech Reports page.

Edit: An improvement of the upper bound of $g(n)$, which might help the OP, is $$g(n)\leqslant\mathrm e^{-np}\sum_{i\geqslant k}\frac{(np)^{i-k}}{(k+1)^{i-k}}=\frac{\mathrm e^{-np}}{1-\frac{np}{k+1}}.$$ Once the idea is understood, one can play with these bounds, and with their variants, for example, for every $(n,p,k)$ such that $np\lt1$, $$1-np\leqslant g(n)\leqslant1-c(k)np,$$ where $c(k)\to1$ when $k\to\infty$.

• I think the first part of your answer can be simplified by using the following $$|f(n)-\hat{f}(n)|\leq d_{TV}(Bin(n,p), Poisson(np)) < p$$ where $d_{TV}$ denotes the total Variation distance. then we have $f(n)\leq \hat{f}(n)+O(p)$ and thus with your bounds $$f(n)\leq \frac{(np)^k}{k!} \frac{1}{1-np}+O(p)=\frac{(np)^k}{k!} (1+\frac{np}{1-np})+O(p)$$ But as we only have $np < 1$ we have that $\frac{np}{1-np}$ can be arbitrarily large.. – user136457 Apr 24 '14 at 9:34
• Simplified? You mean, weakened... The distance in total variation is at most $np^2$ (this is exactly the result my answer uses) and $np^2\lt p$. – Did Apr 24 '14 at 9:36
• Oh ok, sorry. I see, my fault. If I try to get an estimate for your Approximation I get $$f(n) \leq \hat{f}(n)+O(np^2)\leq{(np)^k}{k!}\frac{1}{1−np}+O(np^2) \leq \frac{(np)^k}{k!}(1+\frac{np+O(k!n^{1-k}p^{2-k}(1-np))}{1−np})$$ but I don't see any Chance that I'll get the bound I'm looking for. Is this because my estimates are too weak or might using the estimate $g(n)\leq \frac{1}{1−np}$ be too weak, because this term can get arbitrarily large? by the way: thank you for your help and linking the paper! – user136457 Apr 24 '14 at 10:01
• So I had a look at your answer again and again and tried to get some asymptotic bound out of it. But don't see how I can get this, if I have $$e^{-np}\leq g(n)\leq \frac{1}{1-np}$$ because I don't know how $e^{-np}$ and $\frac{1}{1-np}$ are asymptotically related, as $e^{-np}\leq 1$ and $\frac{1}{1-np}$ is unbounded. It would be a big help if you could tell me, how to Change this in some asymptotics. What I did in the answer above won't help too much (or does it?) because it's an upper bound, but not the same asymptotic lower. So I am really really stuck here! – user136457 Apr 26 '14 at 16:58
• This "$1/(1-np)$ is unbounded" thing seems to obsess you but it is really not a problem. See Edit for one possible extension of the core computations. – Did Apr 26 '14 at 17:27