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.

  • 2
    $\begingroup$ If $k$ and $p$ are fixed and $np \le 1$, there is nothing left to go to $\infty$. How can you talk about asymptotics? $\endgroup$ – Robert Israel Apr 24 '14 at 7:42
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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.. $\endgroup$ – user136457 Apr 24 '14 at 9:34
  • 1
    $\begingroup$ 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$. $\endgroup$ – Did Apr 24 '14 at 9:36
  • $\begingroup$ 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! $\endgroup$ – user136457 Apr 24 '14 at 10:01
  • $\begingroup$ 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! $\endgroup$ – user136457 Apr 26 '14 at 16:58
  • $\begingroup$ 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. $\endgroup$ – Did Apr 26 '14 at 17:27

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.