en>David Eppstein: clean up and source

2012-08-24T00:49:33Z

clean up and source

New page

{{Use dmy dates|date=April 2012}}
The '''law of rare events''' or '''Poisson limit theorem''' gives a [[Poisson distribution|Poisson]] approximation to the [[binomial distribution]], under certain conditions.<ref>Papoulis, Pillai, ''Probability, Random Variables, and Stochastic Processes'', 4th Edition</ref> The theorem was named after [[Siméon Denis Poisson]] (1781–1840).

== The theorem ==
If

:<math>n \rightarrow \infty, p \rightarrow 0</math>, such that <math>np \rightarrow \lambda</math>

then

:<math>\frac{n!}{(n-k)!k!} p^k (1-p)^{n-k} \rightarrow e^{-\lambda}\frac{\lambda^k}{k!}.</math>

== Example ==
Suppose that in an interval [0, 1000], 500 points are placed randomly. Now what is the number of points that will be placed in [0, 10]?

The probabilistically precise way of describing the number of points in the sub-interval would be to describe it as a binomial distribution <math>p_n(k)</math>.

If we look here, the probability (that a random point will be placed in the sub-interval) is <math>p = 10/1000 = 0.01</math>. Here <math>n=500</math> so that <math>np=5</math>.

That is, the probability that <math>k</math> points lie in the sub-interval is

:<math>p_n(k)=\frac{n!}{(n-k)!k!} p^k (1-p)^{n-k}. </math>

But using the Poisson Theorem we can approximate it as

:<math>e^{-\lambda}\frac{\lambda^k}{k!} = e^{-5}\frac{5^k}{k!}.</math>

==Proofs==
Accordingly to [[factorial]]'s [[Stirling's approximation|rate of growth]], we replace factorials of large numbers with approximations:

:<math>\frac{n!}{(n-k)!k!} p^k (1-p)^{n-k} \rightarrow \frac{ \sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{ \sqrt{2\pi \left(n-k\right)}\left(\frac{n-k}{e}\right)^{n-k}k!} p^k (1-p)^{n-k}.</math>
After simplifying the fraction:
:<math>\frac{ \sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{ \sqrt{2\pi \left(n-k\right)}\left(\frac{n-k}{e}\right)^{n-k}k!} p^k (1-p)^{n-k}\rightarrow \frac{ \sqrt{n}n^np^k (1-p)^{n-k}}{ \sqrt{n-k}\left(n-k\right)^{n-k}e^kk!}\rightarrow \frac{n^np^k (1-p)^{n-k}}{\left(n-k\right)^{n-k}e^kk!}.</math>
After using the condition <math>np \rightarrow \lambda</math>:
:<math> \frac{n^np^k (1-p)^{n-k}}{\left(n-k\right)^{n-k}e^kk!} \rightarrow \frac{n^k\left(\frac{\lambda}{n}\right)^k (1-\frac{\lambda}{n})^{n-k}}{\left(1-\frac{k}{n}\right)^{n-k}e^kk!}=\frac{\lambda^k \left(1-\frac{\lambda}{n}\right)^{n-k}}{\left(1-\frac{k}{n}\right)^{n-k}e^kk!}\rightarrow\frac{\lambda^k \left(1-\frac{\lambda}{n}\right)^{n}}{\left(1-\frac{k}{n}\right)^{n}e^kk!}</math>
Apply, that due to <math>n\rightarrow \infty</math> we get <math>\left(1+\frac{x}{n}\right)^n \rightarrow e^x</math>:

<math>\frac{\lambda^k \left(1-\frac{\lambda}{n}\right)^{n}}{\left(1-\frac{k}{n}\right)^{n}e^kk!}\rightarrow\frac{\lambda^k e^{-\lambda}}{e^{-k}e^kk!}=\frac{\lambda^k e^{-\lambda}}{k!}</math>

[[Q.E.D.]]

===Alternative Proof ===
Another proof is possible without needing approximations for the factorials. Since <math>np=\lambda</math>, we can rewrite <math>p=\lambda / n</math>. We now have:
: <math>\lim_{n\to\infty}\frac{n!}{(n-k)!k!} \left(\frac{\lambda}{n}\right)^k \left(1- \frac{\lambda}{n}\right)^{n-k}
= \lim_{n\to\infty}\frac{n(n-1)(n-2)\dots(n-k+1)}{k!} \frac{\lambda^k}{n^k} \left(1- \frac{\lambda}{n}\right)^{n-k} </math>

Taking each of these terms in sequence, <math>n(n-1)(n-2)\dots(n-k+1)=n^k+O\left(n^{k-1}\right)</math>, meaning that <math>\lim_{n\to\infty} \frac{n(n-1)(n-2)\dots(n-k+1)}{n^k k!}= \frac{1}{k!}</math>.

Now <math>\left(1- \frac{\lambda}{n}\right)^{n-k}=\left(1- \frac{\lambda}{n}\right)^{n}\left(1- \frac{\lambda}{n}\right)^{-k}</math>. The first portion of this converges to <math>e^{-\lambda}</math>, and the second portion goes to 1, as <math>\lim_{n\to\infty}\left(1- \frac{\lambda}{n}\right)^{-k}=\lim_{n\to\infty}\left(1- 0\right)^{-k}=1</math>

This leaves us with <math>\frac{1}{k!}\lambda^k e^{-\lambda}</math>. [[Q.E.D.]]

===Proof using Ordinary Generating Functions===
It is also possible to demonstrate the theorem through the use of Ordinary [[Generating Function]]s (OGF). Indeed, the OGF of the binomial distribution is

<math>
G_\mathrm{bin}(x;p,N)
\equiv \sum_{k=0}^{N} \left[ \binom{N}{k} p^k (1-p)^{N-k} \right] x^k
= \Big[ 1 + (x-1)p \Big]^{N}
</math>

by virtue of the [[Binomial Theorem]]. Taking the limit <math>N \rightarrow \infty</math> while keeping the product <math>pN\equiv\lambda</math> constant, we find

<math>
\lim_{N\rightarrow\infty} G_\mathrm{bin}(x;p,N)
= \lim_{N\rightarrow\infty} \Big[ 1 + \frac{\lambda(x-1)}{N} \Big]^{N}
= \mathrm{e}^{\lambda(x-1)}
= \sum_{k=0}^{\infty} \left[ \frac{\mathrm{e}^{-\lambda}\lambda^k}{k!} \right] x^k
</math>

which is simply the OGF for the Poisson distribution (the second equality holds due to the definition of the [[Exponential function]]).

== See also ==
* [[De Moivre–Laplace theorem]]
* [[Le Cam's theorem]]

== References ==
{{reflist}}

[[Category:Articles containing proofs]]
[[Category:Probability theorems]]

Circular coloring - Revision history

en>David Eppstein: clean up and source