Error Bound in Binomial Approximation to Poisson

Question

In formula $(1.1)$ on page $1$ of the book Poisson Approximation by Barbour, Holst, and Janson, they assert the formula $${n \choose k} p^k (1-p)^{n-k} = \frac{(np)^k}{k!} e^{-np} \left(1 + \mathcal{O}(np^2, k^2 n^{-1}) \right).$$ Here $0 \leq k \leq n,$ and $p \in [0,1].$ They say that this can be derived by an "elementary but somewhat involved calculation". How do we derive it? As a first step, how is $\mathcal{O}(a,b)$ defined?

I can rearrange the question into a more usual "big O" problem: we want to show

$$\frac{e^{np} (1-p)^{n-k} n^{\underline{k}}}{n^k} - 1 = \mathcal{O}(np^2, k^2 n^{-1}).$$

Here $n^{\underline{k}} := n (n-1) \cdots (n-k+1).$ I have tried expanding out the expression on the left hand side- the fraction can be written as the product $$\left(\sum_{j=0}^\infty \frac{(np)^j}{j!}\right) \left(\sum_{i=0}^{n-k} (-1)^i p^i {n-k \choose i}\right) \left(\sum_{l=0}^k s(k,k-l) n^{-l} \right),$$ Where $s(k, l)$ is a Stirling number of the first kind. At this point, I don't know how to proceed.

Answer 1

Proposition. (Barbour, Holst, and Janson, (1.1)) $${n \choose k} p^k (1-p)^{n-k} = \frac{(np)^k}{k!} e^{-np} \left(1+\mathcal{O}(np^2, k^2/n) \right).$$ Proof. We need to show $$\frac{n!}{(n-k)! n^k} (1-p)^{n-k} e^{pn} = 1+\mathcal{O}(p^2n, k^2/n).$$ To be concrete, we show there is a constant $C>0$ ($C=5$ works) such that for all $n \in \mathbb{N},$ $k \in\{0,1,...,n\},$ and $p \in [0,1],$ $$1-C \max\{p^2n, k^2/n\} \leq \frac{n!}{(n-k)! n^k} (1-p)^{n-k} e^{pn} \leq 1+C\max\{p^2n, k^2/n \}.$$ Define $$f(k,n,p) = \frac{n!}{(n-k)!n^k} (1-p)^{n-k}e^{pn},$$ $$g(k,n,p) = 1+C\max\{p^2n, k^2/n\},$$ and $$h(k,n,p) = 1-C\max\{p^2n, k^2/n\}.$$

We first handle a series of special cases.

Case 0. $n=0.$ Then $k=0,$ and we use the convention that $k^2/n = 0$ in this case. We have $h(0,0,p) = f(0,0,p) = g(0,0,p) = 1.$

Case 1. $k=0, n \geq 1.$ We use the following two facts: \begin{align} \label{oneplusx} \forall x \in \mathbb{R}, 1+x \leq e^x \ \ \ \ \ (1)\end{align} and \begin{align} \label{oneminusx} \forall x \in \left[0,\frac{1}{2} \right], e^{-x-x^2} \leq 1-x. \ \ \ \ \ (2) \end{align} For the upper bound, we have \begin{align} \nonumber f(0,n,p) &= (1-p)^n e^{pn} \\ \label{bb} &\leq 1 \ \ \ \ \ (3)\\ \nonumber &\leq 1+Cp^2n = g(0,n,p). \end{align} For (3), we have used (1). For the lower bound, if $p \leq \frac{1}{2},$ we have \begin{align} \nonumber f(0,n,p) &=(1-p)^n e^{pn} \\ \label{nbb} &\geq (e^{-p-p^2})^n e^{pn} \ \ \ \ \ (4)\\ \nonumber &= e^{-p^2 n} \\ \label{abb} &\geq 1-p^2n \ \ \ \ \ (5)\\ \nonumber &\geq 1-Cp^2n = h(0,n,p). \end{align} Now, for (4) we used (2), and (5) is another appliction of (1). We also used $C \geq 1$ in the last step. On the other hand, if $p>\frac{1}{2},$ then \begin{align*} f(0,n,p) &= (1-p)^n e^{pn} \\ &\geq 0 \\ &> 1-Cp^2 n = h(0,n,p), \end{align*} where, in the last '$>$' step, we have used $n \geq 1$, $C \geq 4,$ and $p > \frac{1}{2}.$

Case 2. $k=n \geq 1.$ Now the lower bound is immediate: \begin{align*} h(n,n,p) &= 1-Cn \\ &\leq 0 \\ &\leq \frac{n!}{n^n} e^{np} = f(n,n,p). \end{align*} For the first inequality here, we have used $C, n \geq 1.$

As for the upper bound, the hardest case is when $p=1,$ for which we must prove $$\frac{n! e^n}{n^n} \leq 1+Cn.$$ For this, we use the inequality \begin{align} \label{basicStirling} n! \leq (n+1)^{n+1} e^{-n}.\ \ \ \ \ (6)\end{align} This gives us \begin{align} \nonumber f(n,n,1) &= \frac{n! e^n}{n^n} \\ \label{boundfac} &\leq \left( \frac{n+1}{n} \right)^n (n+1) \ \ \ \ \ (7)\\ \nonumber &\leq e(n+1) \\ \label{bigC} &\leq 1+Cn \ \ \ \ \ (8)\\ \nonumber &=g(n,n,p). \end{align} Here, for (7) we have used (6), and for (8) we are using $n \geq 1$ as well as $C \geq 2e-1.$ This completes the proof of Case 2.

Now fix $n \geq 2$ and $1 \leq k \leq n-1.$ We note that $f$ is $\mathcal{C}^1$ as a function of $p$ on $(0,1)$ and continuous at $p=0,1$. We have \begin{align} \label{deriv} \frac{df}{dp} = \frac{n!}{(n-k)! n^k} \left( n(1-p)^{n-k}e^{np} - (n-k)(1-p)^{n-k-1} e^{np} \right).\ \ \ \ \ (9)\end{align} In particular, \begin{align} \label{pzero} &f(k,n,0) = \frac{n!}{(n-k)! n^k} \ \ \ \ \ (10)\\ \label{pone} &f(k,n,1) = 0 \ \ \ \ \ (11)\\ \label{derivleftineq} &\forall p \in \left(0,\frac{k}{n}\right), \frac{df}{dp} > 0, \text{ and} \ \ \ \ \ (12)\\ \label{derivrightineq} &\forall p \in \left(\frac{k}{n}, 1\right), \frac{df}{dp} < 0.\ \ \ \ \ (13) \end{align} Therefore $f$ is nondecreasing on $[0,\frac{k}{n}]$ and nonincreasing on $[\frac{k}{n},1].$ Meanwhile, $g$ and $h$ are constant for $p \in \left[0,\frac{k}{n}\right]$, whereas for $p>\frac{k}{n},$ $g$ is increasing and $h$ is decreasing.

In view of the above, it remains to show: (A) $f(k,n,0) \geq h(k,n,0),$ i.e. $$\frac{n!}{(n-k)! n^k} \geq 1-Ck^2/n,$$ (B) $f(k,n,\frac{k}{n}) \leq g(k,n,\frac{k}{n}),$ i.e. $$\frac{n!}{(n-k)! n^k} \left(1-\frac{k}{n}\right)^{n-k} e^{k} \leq 1+Ck^2/n,$$ and (C) for all $p \in [\frac{k}{n},1],$ $f(k,n,p) \geq h(k,n,p).$

For (A), we argue as follows. \begin{align*} \frac{n!}{(n-k)! n^k} &\geq \left(\frac{n-k}{n}\right)^k \\ &\geq 1-k^2/n \\ &\geq 1-Ck^2/n = h(k,n,0). \end{align*}

Next, for (B), we need a stronger inequality coming from Stirling, \begin{align} \label{strongStirling} \frac{n!}{(n-k)!} \leq \frac{n^{n+\frac{1}{2}}}{(n-k)^{n-k+\frac{1}{2}}} e^{-k}. \ \ \ \ \ (14)\end{align} We also use the general inequality, \begin{align} \label{sqrtineq} \forall x \geq 0, \sqrt{1+x} \leq 1+\frac{x}{2}. \ \ \ \ \ (15)\end{align} Therefore \begin{align} \label{useStrl} \frac{n!}{(n-k)! n^k} \left(1-\frac{k}{n}\right)^{n-k} e^k &\leq \frac{n^{n+\frac{1}{2}} e^{-k}}{(n-k)^{n-k+\frac{1}{2}} n^k} e^k \ \ \ \ \ (16)\\ \nonumber &= \sqrt{\frac{n}{n-k}} \\ \label{usesqrt} &\leq 1+\frac{k}{2(n-k)} \ \ \ \ \ (17)\\ \label{quadineq} &\leq 1+k^2/n \ \ \ \ \ (18)\\ \nonumber &\leq 1+Ck^2/n = g\left(k,n,\frac{k}{n}\right). \end{align} Here (16) is the application of (14), (17) is an application of (15), and (18) makes use of the fact that $1 \leq k \leq n-1$ and $n \geq 2.$

Finally, for (C), we note that if $p > \frac{1}{\sqrt{n}},$ then $h(k,n,p) = 1 - Cp^2 n < 0.$ Here we have used $C \geq 1$. Since $f(k,n,p)$ is always nonnegative, we are done in that case. It remains to show that for $p \in [\frac{k}{n}, \frac{1}{\sqrt{n}}],$ $$f(k,n,p) \geq 1-Cp^2n.$$ We remark that, since $n \geq 2,$ $p \leq \frac{1}{\sqrt{2}}.$ So we'll apply the following fact: \begin{align} \label{oneminusxredux} \forall p \in \left[0,\frac{1}{\sqrt{2}} \right], 1-p \geq e^{-p-\sqrt{2}p}. \ \ \ \ \ (19)\end{align} We have: \begin{align} \nonumber f(k,n,p) &= \frac{n!}{(n-k)! n^k} (1-p)^{n-k} e^{pn} \\ \nonumber &\geq \left(1-\frac{k^2}{n}\right) (1-p)^{n-k} e^{pn} \\ \label{againoneminusx} &\geq \left(1-\frac{k^2}{n}\right) (e^{-p- \sqrt{2} p^2})^{n-k} e^{pn} \ \ \ \ \ (20)\\ \nonumber &\geq \left(1-\frac{k^2}{n}\right) e^{-\sqrt{2} p^2n} \\ \label{againoneplusx} &\geq \left(1-\frac{k^2}{n} \right) (1- \sqrt{2} p^2n) \ \ \ \ \ (21)\\ \nonumber &\geq 1-\frac{k^2}{n} - \sqrt{2} p^2n \\ \label{rangeofp} &\geq 1- (1+\sqrt{2})p^2n \ \ \ \ \ (22)\\ \nonumber &\geq 1-Cp^2n = h(k,n,p). \end{align} Here (20) is the promised application of (19), (21) is an application of (1), and (22) makes use of the fact that $k/n \leq p.$ In the last step, we've used $C \geq 1+\sqrt{2}.$

Answer 2

My favorite is generating functions (G F) approach.

G F of the binomial distribution

$$P(s)=\sum_{k=0}^{n}{n \choose k}(1-p)^{n-k}p^k s^k=(1-p+ps)^n$$

Let's introduce the notation $\lambda= np$

$$P(s)=\left (1 -\lambda\frac{1-s}{n} \right )^n$$

Now,

$$P(s)\rightarrow e^{-\lambda (1-s)}=e^{-\lambda}e^{\lambda s} $$

as $n\rightarrow \infty$

So we came to the G F of the poisson distribution.

Improvements

Actually, I don't know what $\mathcal{O}(a,b)$ is but as a physicist i can suggest the following elementary procedures to estimate the precision of the expression

$$\frac{{n \choose k}(1-p)^{n-k}p^k }{e^{-\lambda}\frac{\lambda^k}{k!}}$$

where $\lambda= np$

After taking the logarithmic derivative of the expression we get

$$\ln( n-k )+\frac{1}{2( n-k )}+\ln\frac{p}{\lambda (1-p)}$$

(Stirling approximation $n!=\sqrt{2\pi n}\left (\frac{n}{e}\right )^n$ was used.)

Equating the result to zero and solving for k we get

$$k=np=\lambda$$

(Unimportant term $\frac{1}{2( n-k )}$ was ignored)

At $k=np=\lambda$ the initial expression has maximum equal to

$$\frac{e^{\lambda} \lambda! }{\sqrt{2\pi \lambda}\lambda^{\lambda}}=1+\frac{1}{12\lambda}+\frac{1}{288\lambda^2}+...$$

Here we used the correction terms of the Stirling approximation.

Finally, we get the following estimate

$$\frac{{n \choose k}(1-p)^{n-k}p^k }{e^{-\lambda}\frac{\lambda^k}{k!}}<1+\frac{1}{12\lambda}+\frac{1}{288\lambda^2}+...$$ $$1\leq \lambda$$