Skip to content

The De Moivre-Laplace Theorem

De Moivre–Laplace theorem, which is a special case of the central limit theorem, states that the normal distribution may be used as an approximation to the binomial distribution under certain conditions. The theorem appeared in the second edition of The Doctrine of Chances by Abraham de Moivre, published in 1738. Although de Moivre did not use the term "Bernoulli trials", he wrote about the probability distribution of the number of times "heads" appears when a coin is tossed 3600 times.
THE DE MOIVRE-LAPLACE THEOREM
If a<ba<b then as n→∞n \rightarrow \infty
P(a≤Snn≤b)→∫ab12πe−x2/2dx\begin{equation*}\mathbb{P}\left(a \leq \frac{S_n}{\sqrt{n}} \leq b\right) \rightarrow \int_a^b\frac{1}{\sqrt{2\pi}} e^{-x^2 / 2} \text{d} x\end{equation*}
Let X1,X2,…X_1,X_2,\ldots be i.i.d. random variables such that
P(Xi=1)=P(Xi=−1)=12,i≥1.\begin{equation*}\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)=\tfrac12, \qquad i\ge 1.\end{equation*}
and let Sn=∑k=1nXkS_n= \sum_{k=1}^n X_k. In words, we are betting 1 dollar on the flipping of a fair coin and SnS_n is our winnings at time nn.
Sum distribution
Let X1,X2,…X_1, X_2, \ldots be as above, we are interested in the distribution of the partial sums
Sn=X1+X2+⋯+Xn.\begin{equation*}S_n = X_1 + X_2 + \cdots + X_n .\end{equation*}
To make the combinatorics transparent, it is convenient to consider the probability P(S2n=2k)\mathbb{P}\left(S_{2n}=2k\right). The event S2n=2kS_{2n}=2k happens if and only if among the first 2n2n variables there are exactly n+kn+k values equal to +1+1 and n−kn-k values equal to −1-1. Therefore
P(S2n=2k)=(2nn+k)2−2n\begin{equation*}\mathbb{P}\left(S_{2 n}=2 k\right)=\binom{2n}{n+k}2^{-2 n}\end{equation*}
The binomial coefficient counts the number of such outcomes, and the factor 2−2n2^{-2n} is the probability of each one.
If we visualize these probabilities and then increase nn, a clear pattern starts to emerge: the binomial probabilities form a bell-shaped curve, and this curve becomes smoother as nn grows. The transition from a discrete, jagged distribution to a smooth symmetric bell curve is the phenomenon that the De Moivre-Laplace theorem makes precise.

The foolowing proof is taken from [Durrett2019] p. 98-99

The proof strategy for the theorem is as follows: initially, we approximate the probability P(S2n=2k)\mathbb{P}\left(S_{2 n}=2 k\right) for a single point. Then, we proceed to calculate the probability for the interval P(a≤S2n2n≤b)\mathbb{P}\left(a \leq \frac{S_{2n}}{\sqrt{2n}} \leq b \right).
LEMMA
If 2k/2n→x2 k / \sqrt{2n} \rightarrow x then P(S2n=2k)∼1πne−x2/2\mathbb{P}\left(S_{2 n}=2 k\right) \sim\frac{1}{\sqrt{\pi n}} e^{-x^2 / 2}.
By Stirling's formula we have
n!∼2πn(ne)n as n→∞\begin{equation*}n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \quad \text{ as } n \rightarrow \infty\end{equation*}
where an∼bna_n \sim b_n means an/bn→1a_n / b_n \rightarrow 1 as n→∞n \rightarrow \infty. Now we have
(2nn+k)=(2n)!(n+k)!(n−k)!∼(2n)2n(n+k)n+k(n−k)n−k⋅2π(2n)2π(n+k)2π(n−k)\begin{equation*}\binom{2n}{n+k}=\frac{(2 n) !}{(n+k) !(n-k) !} \sim \frac{(2 n)^{2 n}}{(n+k)^{n+k}(n-k)^{n-k}} \cdot \frac{\sqrt{2 \pi(2 n)}}{\sqrt{2 \pi(n+k)}\sqrt{2 \pi(n-k)}}\end{equation*}
and we get
(2nn+k)2−2n∼(1+kn)−n−k⋅(1−kn)−n+k⋅1πn⋅11+kn⋅11−kn\begin{equation*} \begin{aligned}\binom{2n}{n+k}2^{-2 n} & \sim\left(1+\frac{k}{n}\right)^{-n-k} \cdot\left(1-\frac{k}{n}\right)^{-n+k} \cdot\frac{1}{\sqrt{\pi n}} \cdot\frac{1}{\sqrt{1+\frac{k}{n}}} \cdot\frac{1}{\sqrt{1-\frac{k}{n}}} \end{aligned}\end{equation*}
The first two terms on the right can be transformed by the formula for the difference of two squares
(1+kn)−n−k⋅(1−kn)−n+k=(1−k2n2)−n⋅(1+kn)−k⋅(1−kn)k\begin{equation}\left(1+\frac{k}{n}\right)^{-n-k} \cdot\left(1-\frac{k}{n}\right)^{-n+k}=\left(1-\frac{k^2}{n^2}\right)^{-n} \cdot\left(1+\frac{k}{n}\right)^{-k} \cdot\left(1-\frac{k}{n}\right)^k\end{equation}
We repeatedly use the fact that if un→0u_n\to 0 and vnun→cv_nu_n\to c, then
(1+un)vn→ec.\begin{equation*}(1+u_n)^{v_n}\to e^c.\end{equation*}
Assume that
2k2n→x.\begin{equation*}\frac{2k}{\sqrt{2n}} \to x.\end{equation*}
Equivalently, k=xn/2+o(n)k=x \sqrt{n / 2}+o(\sqrt{n}), so
(1−k2n2)−n=(1−x22n)−n→ex2/2,(1+kn)−k=(1+x2n)−xn/2→e−x2/2,(1−kn)k=(1−x2n)xn/2→e−x2/2.\begin{equation*} \begin{aligned}& \left(1-\frac{k^2}{n^2}\right)^{-n}=\left(1-\frac{x^2}{2 n}\right)^{-n} \rightarrow e^{x^2 / 2}, \\& \left(1+\frac{k}{n}\right)^{-k}=\left(1+\frac{x}{\sqrt{2n}}\right)^{-x \sqrt{n / 2}} \rightarrow e^{-x^2 / 2}, \\& \left(1-\frac{k}{n}\right)^k=\left(1-\frac{x}{\sqrt{2n}}\right)^{x \sqrt{n / 2}} \rightarrow e^{-x^2 / 2}. \end{aligned}\end{equation*}
For this choice of k,k/n→0k, k / n \rightarrow 0, so
11+kn⋅11−kn→1\begin{equation*}\frac{1}{\sqrt{1+\frac{k}{n}}} \cdot\frac{1}{\sqrt{1-\frac{k}{n}}} \rightarrow 1\end{equation*}
and putting things together gives:
P(S2n=2k)∼1πne−x2/2\begin{equation*}\mathbb{P}\left(S_{2 n}=2 k\right) \sim \frac{1}{\sqrt{\pi n}} e^{-x^2 / 2}\end{equation*}
Our next step is to compute
P(a2n≤S2n≤b2n)=∑m∈[a2n,b2n]∩2ZP(S2n=m)\begin{equation*}\mathbb{P}\left(a \sqrt{2n} \leq S_{2 n} \leq b \sqrt{2n}\right)=\sum_{m \in [a \sqrt{2n}, b \sqrt{2n}] \cap 2 \mathbf{Z}} \mathbb{P}\left(S_{2 n}=m\right)\end{equation*}
Changing variables m=x2nm=x \sqrt{2n}, we have Δx=22n=2n\Delta x=\frac{2}{\sqrt{2n}}=\sqrt{\frac{2}{n}}, and the above is
P(a2n≤S2n≤b2n)≈∑x∈[a,b]∩(2Z/2n)φ(x) Δx,\begin{equation*}\mathbb{P}\left(a \sqrt{2n} \leq S_{2 n} \leq b \sqrt{2n}\right) \approx \sum_{x \in [a, b] \cap (2 \mathbf{Z} / \sqrt{2n})}\varphi(x)\,\Delta x,\end{equation*}
where
φ(x)=12πe−x2/2\begin{equation*}\varphi(x)=\frac{1}{\sqrt{2 \pi}} e^{-x^2 / 2}\end{equation*}
and 2Z/2n={2z/2n:z∈Z}2 \mathbf{Z} / \sqrt{2n}=\{2 z / \sqrt{2n}: z \in \mathbf{Z}\}. Thus, if nn is large the sum above is
≈∫ab12πe−x2/2dx\begin{equation*}\approx \int_a^b\frac{1}{\sqrt{2 \pi}} e^{-x^2 / 2} d x\end{equation*}
The integrand is the density of the (standard) normal distribution, so changing notation we can write the last quantity as P(a≤χ≤b)\mathbb{P}(a \leq \chi \leq b) where χ\chi is a random variable with that distribution. We proved the De Moivre-Laplace Theorem. To remove the restriction to even integers observe
S2n+1=S2n+X2n+1,X2n+1∈{−1,1}.\begin{equation*}S_{2n+1}=S_{2 n}+X_{2n+1}, \qquad X_{2n+1}\in\{-1,1\}.\end{equation*}
□\Box

References