TAOCP 1.2.10 Exercise 15
The Poisson distribution with parameter $\mu$ assigns probabilities p_k = e^{-\mu}\frac{\mu^k}{k!
Section 1.2.10: Analysis of an Algorithm
Exercise 15. [HM23] When the probability that some quantity has the value $k$ is $e^{-\mu}(\mu^k/k!)$, it is said to have the Poisson distribution with mean $\mu$.
a) What is the generating function for this set of probabilities?
b) What are the values of the semi-invariants?
c) Show that as $n\to\infty$ the Poisson distribution with mean $np$ approaches the normal distribution in the sense of exercise 13.
Verified: yes
Solve time: 1m38s
Solution
The Poisson distribution with parameter $\mu$ assigns probabilities
$$ p_k = e^{-\mu}\frac{\mu^k}{k!}, \qquad k \ge 0. $$
a) Generating function
The generating function is
$$ G(z) = \sum_{k \ge 0} p_k z^k = \sum_{k \ge 0} e^{-\mu}\frac{\mu^k}{k!} z^k. $$
Factor $e^{-\mu}$ and rewrite:
$$ G(z) = e^{-\mu} \sum_{k \ge 0} \frac{(\mu z)^k}{k!}. $$
The exponential series gives $\sum_{k \ge 0} (\mu z)^k/k! = e^{\mu z}$, hence
$$ G(z) = e^{-\mu} e^{\mu z} = e^{\mu(z-1)}. $$
Thus
$$ \boxed{G(z) = e^{\mu(z-1)}}. $$
b) Semi-invariants
Define
$$ K(t) = \log G(e^t). $$
From part (a),
$$ G(e^t) = \exp(\mu(e^t - 1)), $$
so
$$ K(t) = \mu(e^t - 1). $$
Expand $e^t$:
$$ e^t - 1 = \sum_{n \ge 1} \frac{t^n}{n!}. $$
Hence
$$ K(t) = \sum_{n \ge 1} \mu \frac{t^n}{n!}. $$
By definition of semi-invariants (cumulants),
$$ K(t) = \sum_{n \ge 1} \kappa_n \frac{t^n}{n!}, $$
so comparison of coefficients yields
$$ \kappa_n = \mu \quad (n \ge 1). $$
Thus
$$ \boxed{\kappa_n = \mu \text{ for all } n \ge 1}. $$
c) Limit to the normal distribution
Consider the Poisson distribution with mean $np$, so $\mu = np$. Its generating function is
$$ G(z) = \exp(np(z-1)). $$
Let
$$ \sigma = \sqrt{np}. $$
From Exercise 13, the required limit is
$$ \lim_{n \to \infty} e^{-it\mu/\sigma} G(e^{it/\sigma}). $$
Substitute $\mu = np$ and $G$:
$$ e^{-it\mu/\sigma} G(e^{it/\sigma}) = \exp!\left(-it\frac{np}{\sqrt{np}} + np(e^{it/\sqrt{np}} - 1)\right). $$
Simplify the linear term:
$$ -it\frac{np}{\sqrt{np}} = -it\sqrt{np}. $$
Hence the exponent equals
$$ np\left(e^{it/\sqrt{np}} - 1 - \frac{it}{\sqrt{np}}\right). $$
Expand $e^{x}$ at $x = it/\sqrt{np}$:
$$ e^x = 1 + x + \frac{x^2}{2} + O(x^3). $$
Therefore
$$ e^x - 1 - x = \frac{x^2}{2} + O(x^3). $$
With $x = it/\sqrt{np}$,
$$ \frac{x^2}{2} = -\frac{t^2}{2np}, \qquad x^3 = O!\left((np)^{-3/2}\right). $$
Multiply by $np$:
$$ np\left(e^x - 1 - x\right) = -\frac{t^2}{2} + O!\left((np)^{-1/2}\right). $$
As $n \to \infty$, the error term tends to $0$, hence the exponent converges to $-t^2/2$. Therefore
$$ \lim_{n \to \infty} e^{-it\mu/\sigma} G(e^{it/\sigma}) = e^{-t^2/2}. $$
This matches the criterion of Exercise 13, so the Poisson distribution with mean $np$ approaches the normal distribution.
This completes the proof. ∎