Skip to content

De Moivre-Laplace Theorem

The 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.
Let X1,X2,…X_1,X_2,\ldots be i.i.d. random variables such that
P(Xi=1)=P(Xi=−1)=12.\begin{equation*}\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)=\tfrac12.\end{equation*}
and let Sn=∑k=1nXkS_n= \sum_{k=1}^n X_k. Informally, we are betting 1 dollar on the flipping of a fair coin and SnS_n is our winnings at time nn.
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*}

Motivation

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.

Proof of De Moivre-Laplace Theorem

The following proof is taken from Durrett [Durrett2019], pp. 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).

Approximation of P(S2n=2k)\mathbb{P}\left(S_{2 n}=2 k\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*}

Approximation of P(a≤S2n/2n≤b)\mathbb{P}\left(a \leq S_{2 n} / \sqrt{2n} \leq b \right)

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\} \qquad \Box.\end{equation*}

References

  • [Durrett2019]Durrett, Rick. Probability: Theory and Examples. Fifth edition. Cambridge University Press, 2019. PDF.