TAOCP 1.2.10 Exercise 14
Let G_n(z)=(q+pz)^n,\qquad q=1-p.
Section 1.2.10: Analysis of an Algorithm
Exercise 14. [HM30] (A. de Moivre.) Using the conventions of the previous exercise, show that the binomial distribution $G_n(z)$ given by Eq. (18) approaches the normal distribution.
Verified: yes
Solve time: 47s
Setup
Let
$$ G_n(z)=(q+pz)^n,\qquad q=1-p. $$
From the preceding analysis of the binomial process, the mean and variance are
$$ \mu_n = pn,\qquad \sigma_n^2 = pqn. $$
The expression to be evaluated is
$$ \Phi_n(t)=e^{-it\mu_n/\sigma_n},G_n!\left(e^{it/\sigma_n}\right). $$
The goal is to prove
$$ \lim_{n\to\infty}\Phi_n(t)=e^{-t^2/2}. $$
Solution
Define
$$ f(u)=\log(q+pe^u). $$
Then
$$ G_n(e^{it/\sigma_n})=\exp!\bigl(n f(it/\sigma_n)\bigr), $$
and therefore
$$ \Phi_n(t)=\exp!\left(n f!\left(\frac{it}{\sigma_n}\right)-\frac{it\mu_n}{\sigma_n}\right). $$
It suffices to determine the limit of the exponent.
The derivatives of $f$ at $u=0$ are computed directly. From $f(u)=\log(q+pe^u)$,
$$ f'(u)=\frac{pe^u}{q+pe^u}. $$
Hence
$$ f'(0)=p. $$
Differentiating again,
$$ f''(u)=\frac{pe^u(q+pe^u)-pe^u(pe^u)}{(q+pe^u)^2} =\frac{pq e^u}{(q+pe^u)^2}, $$
so
$$ f''(0)=pq. $$
A Taylor expansion at $u=0$ gives
$$ f(u)=p u+\frac{pq}{2}u^2+o(u^2)\quad (u\to 0). $$
Substituting $u=it/\sigma_n$,
$$ f!\left(\frac{it}{\sigma_n}\right) = \frac{ipt}{\sigma_n} - \frac{pq}{2}\frac{t^2}{\sigma_n^2} + o!\left(\frac{1}{\sigma_n^2}\right). $$
Multiplying by $n$,
$$ n f!\left(\frac{it}{\sigma_n}\right) = \frac{iptn}{\sigma_n} - \frac{n pq}{2\sigma_n^2}t^2 + o(1). $$
Since $\sigma_n^2=pqn$,
$$ \frac{n pq}{\sigma_n^2}=1, $$
and therefore
$$ n f!\left(\frac{it}{\sigma_n}\right) = \frac{iptn}{\sigma_n} - \frac{t^2}{2} + o(1). $$
The exponent in $\Phi_n(t)$ becomes
$$ n f!\left(\frac{it}{\sigma_n}\right)-\frac{it\mu_n}{\sigma_n} = \frac{iptn}{\sigma_n}-\frac{itpn}{\sigma_n}-\frac{t^2}{2}+o(1) = -\frac{t^2}{2}+o(1). $$
Hence
$$ \Phi_n(t)=\exp!\left(-\frac{t^2}{2}+o(1)\right), $$
and taking the limit yields
$$ \lim_{n\to\infty}\Phi_n(t)=e^{-t^2/2}. $$
This completes the proof. ∎
Verification
The cancellation in the linear term uses
$$ \mu_n = pn,\qquad \sigma_n=\sqrt{pqn}, $$
so that
$$ \frac{it\mu_n}{\sigma_n}=\frac{iptn}{\sigma_n}. $$
The quadratic coefficient depends only on $f''(0)=pq$, which yields
$$ \frac{n}{2}f''(0)\frac{t^2}{\sigma_n^2}=\frac{t^2}{2}. $$
All remaining terms are $o(1)$ since $u=it/\sigma_n$ satisfies $u\to 0$ and $n u^3\to 0$.
Notes
The argument depends only on the second-order expansion of $\log(q+pe^u)$ at $u=0$, so higher derivatives of $f$ do not affect the limit after normalization by $\mu_n$ and $\sigma_n$.