De Moivre–Laplace theorem

Theorem

As n grows large, for k in the neighborhood of np we can approximate : {n \choose k}, p^k q^{n-k} \simeq \frac{1}{\sqrt{2 \pi npq}},e^{-\frac{(k-np)^2}{2npq}}, \qquad p+q=1,\ p, q 0 in the sense that the ratio of the left-hand side to the right-hand side converges to 1 as n → ∞.

Proof

The theorem can be more rigorously stated as follows: \left(X!,-!, np\right)!/!\sqrt{npq}, with \textstyle X a binomially distributed random variable, approaches the standard normal as n!\to!\infty, with the ratio of the probability mass of X to the limiting normal density being 1. This can be shown for an arbitrary nonzero and finite point c. On the unscaled curve for X, this would be a point k given by

:k=np+c\sqrt{npq}

For example, with c at 3, k stays 3 standard deviations from the mean in the unscaled curve.

The normal distribution with mean \mu and standard deviation \sigma is defined by the differential equation (DE)

:f'!(x)!=!-!,\frac{x-\mu}{\sigma^2}f(x) with an initial condition set by the probability axiom \int_{-\infty}^{\infty}!f(x),dx!=!1. The binomial distribution limit approaches the normal if the binomial satisfies this DE. As the binomial is discrete the equation starts as a difference equation whose limit morphs to a DE. Difference equations use the discrete derivative, \textstyle p(k!+!1)!-!p(k), the change for step size 1. As \textstyle k!\to!\infty, the discrete derivative becomes the continuous derivative. Hence the proof need show only that, for the unscaled binomial distribution,

:\frac{p(n, k+1)-p(n,k)}{p(n,k)}!\cdot! \left(-\frac{\sigma^2}{k-\mu}\right) !\to! 1 as n!\to!\infty, where p(n,k) = {n \choose k}, p^k q^{n-k}, \mu = np, and \sigma = \sqrt{npq}.

The required result can be shown directly:

: \begin{align} \frac{p\left(n, k + 1\right) - p\left(n, k\right)}{p\left(n, k\right)}\frac{npq}{np!,-!,k}!&= \frac{np - k -q}{kq+q}\frac{\sqrt{npq}}{-c} \ &= \frac{-c\sqrt{npq} -q}{npq + cq\sqrt{npq}+q}\frac{\sqrt{npq}}{-c} \ & \to 1 \end{align}

The last holds because the term -cnpq dominates both the denominator and the numerator as n!\to!\infty.

As \textstyle k takes just integral values, the constant \textstyle c is subject to a rounding error. However, the maximum of this error, \textstyle {0.5}/!\sqrt{npq}, is a vanishing value.

Alternative proof

The proof consists of transforming the left-hand side (in the statement of the theorem) to the right-hand side by three approximations.

First, according to Stirling's formula, the factorial of a large number n can be replaced with the approximation

: n! \simeq n^n e^{-n}\sqrt{2 \pi n}\qquad \text{as } n \to \infty.

Thus

: \begin{align}{n \choose k} p^k q^{n-k} & = \frac{n!}{k!(n-k)!} p^k q^{n-k} \& \simeq \frac{n^n e^{-n}\sqrt{2\pi n} }{k^ke^{-k}\sqrt{2\pi k} (n-k)^{n-k}e^{-(n-k)}\sqrt{2\pi (n-k)}} p^k q^{n-k}\&=\sqrt{\frac{n}{2\pi k\left(n-k\right)}}\frac{n^n}{k^k\left(n-k\right)^{n-k}}p^kq^{n-k}\&=\sqrt{\frac{n}{2\pi k\left(n-k\right)}}\left(\frac{np}{k}\right)^k\left(\frac{nq}{n-k}\right)^{n-k}\end{align}

Next, the approximation \tfrac{k}{n} \to p is used to match the square root above to the desired square root on the right-hand side.

: \begin{align}{n \choose k} p^k q^{n-k} & \simeq \sqrt{\frac{1}{2\pi n\frac{k}{n}\left(1-\frac{k}{n}\right)}}\left(\frac{np}{k}\right)^{k} \left(\frac{nq}{n-k}\right)^{n-k}\&\simeq\frac{1}{\sqrt {2\pi npq}}\left(\frac{np}{k}\right)^{k} \left(\frac{nq}{n-k}\right)^{n-k} \qquad p+q=1\ \end{align}

Finally, the expression is rewritten as an exponential, x = \frac{k-np}{\sqrt{npq}} (the standardized value for k) is introduced, and the Taylor Series approximation for ln(1+w) is used:

: \ln\left(1+w\right)\simeq w-\frac{w^2}{2}+\frac{w^3}{3}-\cdots

Then

: \begin{align}{n \choose k} p^k q^{n-k} &\simeq \frac{1}{\sqrt {2\pi npq}}\exp\left{\ln \left( \left(\frac{np}{k}\right)^{k} \right)+\ln \left( \left(\frac{nq}{n-k}\right)^{n-k}\right)\right}\ &=\frac{1}{\sqrt {2\pi npq}}\exp\left{-k\ln\left(\frac{k}{np}\right)+(k-n)\ln \left(\frac{n-k}{nq}\right)\right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{-k\ln\left(\frac{np+x\sqrt{npq}}{np}\right)+(k-n)\ln \left(\frac{n-np-x\sqrt{npq}}{nq}\right)\right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{-k\ln\left({1+x\sqrt\frac{q}{np}}\right)+(k-n)\ln \left({1-x\sqrt\frac{p}{nq}}\right)\right}\qquad p+q=1\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{-k\left({x\sqrt\frac{q}{np}}-\frac{x^2q}{2np}+\cdots\right)+(k-n) \left({-x\sqrt\frac{p}{nq}-\frac{x^2p}{2nq}}-\cdots\right)\right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{\left(-np-x\sqrt{npq}\right)\left({x\sqrt\frac{q}{np}}-\frac{x^2q}{2np}+\cdots\right)+\left(np+x\sqrt{npq}-n\right) \left(-x\sqrt\frac{p}{nq}-\frac{x^2p}{2nq}-\cdots\right)\right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{\left(-np-x\sqrt{npq}\right)\left(x\sqrt\frac{q}{np}-\frac{x^2q}{2np}+\cdots\right)-\left(nq-x\sqrt{npq}\right) \left(-x\sqrt\frac{p}{nq}-\frac{x^2p}{2nq}-\cdots\right)\right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{\left(-x\sqrt{npq}+\frac{1}{2}x^2q-x^2q+\cdots\right)+\left(x\sqrt{npq}+\frac{1}{2}x^2p-x^2p-\cdots\right) \right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{-\frac{1}{2}x^2q-\frac{1}{2}x^2p-\cdots\right}\&=\frac{1}{\sqrt {2\pi npq}}\exp\left{-\frac{1}{2}x^2(p+q)-\cdots\right}\&\simeq\frac{1}{\sqrt {2\pi npq}}\exp\left{-\frac{1}{2}x^2\right}\&=\frac{1}{\sqrt {2\pi npq}}e^\frac{-(k-np)^2}{2npq}\ \end{align}

Each "\simeq" in the above argument is a statement that two quantities are asymptotically equivalent as n increases, in the same sense as in the original statement of the theorem—i.e., that the ratio of each pair of quantities approaches 1 as n → ∞.

Notes

References

1. Walker, Helen M. (1985). "A source book in mathematics". Dover.
2. (2002). "Probability, Random Variables, and Stochastic Processes". McGraw-Hill.
3. Feller, W.. (1968). "An Introduction to Probability Theory and Its Applications". Wiley.
4. (2018). "Normal limit of the binomial via the discrete derivative". The College Mathematics Journal.