De Moivre–Laplace theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Within a system whose bins are filled according to the binomial distribution (such as the "Bean machine"), we have a demonstration of what happens when we let the number of trials (which are dropped "beans" here) n go to infinity: a shape representing the probability distribution of k successes in n trials asymptotically becomes the Gaussian distribution of mean np and variance np(1-p), given successes occur with probability p.
Consider tossing a set of n coins k times and counting the number of tails in the array of n coins after each toss: the vertical axis above then represents the number of times a certain number of tails (given by the horizontal axis) came up in each of the k tosses averaged as k → ∞. The heights are thus probabilities that a certain number of tails comes up. According to the De Moivre-Laplace theorem, as n grows large, the shape of this distribution, given for finite n by the binomial distribution, begins to resemble the smooth Gaussian curve of the normal distribution.

In probability theory, the de Moivre–Laplace theorem is a normal approximation to the binomial distribution. It is a special case of the central limit theorem. It states that the binomial distribution of the number of "successes" in n independent Bernoulli trials with probability p of success on each trial is approximately a normal distribution with mean np and standard deviation np(1-p), if n is very large and some conditions are satisfied.

The theorem appeared in the second edition of The Doctrine of Chances by Abraham de Moivre, published in 1738. The "Bernoulli trials" were not so-called in that book, but rather de Moivre wrote about the probability distribution of the number of times "heads" appears when a coin is tossed 3600 times.[1]

This is one derivation of the particular Gaussian function used in the normal distribution.


As n grows large, for k in the neighborhood of np we can approximate[2][3]

{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 → ∞.


Note that k cannot be fixed or it would quickly fall outside the range of interest as n → ∞. What is needed is to let k vary but always be a fixed number of standard deviations from the mean, so that it is always associated with the same point on the standard normal distribution. We can do this by defining


for some fixed x. Then, for example, when x = 1, k will always be 1 standard deviation from the mean. From this definition we have the approximations knp and \tfrac{k}{n} \to p as n → ∞.

However, the left-hand side requires that k be an integer. Keeping the notation but assuming that k is the nearest integer given by the definition, this is seen to be inconsequential in the limit by noting that as n → ∞ the change in x required to make k an integer becomes small and successive integer values of k produce converging values on the right-hand side:

\frac{\frac{1}{\sqrt{2\pi npq}}e^\frac{-(k+1-np)^2}{2npq}}{\frac{1}{\sqrt{2\pi npq}}e^\frac{-(k-np)^2}{2npq}}=e^\frac{2np-2k-1}{2npq}\simeq e^\frac{-x}{2\sqrt{npq}}\simeq e^0= 1\qquad \text{as } n\to \infty.

The proof consists of transforming the left-hand side to the right-hand side by three approximations.

First, according to Stirling's formula, we can replace the factorial of a large number n with the approximation:

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


\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, use the approximation \tfrac{k}{n} \to p to match the root above to the desired 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, rewrite the expression as an exponential and use the Taylor Series approximation for ln(1+x):

 \ln\left(1+x\right)\simeq x-\frac{x^2}{2}+\frac{x^3}{3}-...


\begin{align}{n \choose k} p^k q^{n-k} &\simeq \frac{1}{\sqrt {2\pi npq}}\exp\left\{\ln\left(\frac{np}{k}\right)^{k}+\ln \left(\frac{nq}{n-k}\right)^{n-k}\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}+...\right)+(k-n) \left({-x\sqrt\frac{p}{nq}-\frac{x^2p}{2nq}}-...\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}+...\right)+\left(np+x\sqrt{npq}-n\right) \left(-x\sqrt\frac{p}{nq}-\frac{x^2p}{2nq}-...\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}+...\right)-\left(nq-x\sqrt{npq}\right) \left(-x\sqrt\frac{p}{nq}-\frac{x^2p}{2nq}-...\right)\right\}\\&=\frac{1}{\sqrt {2\pi npq}}\exp\left\{\left(-x\sqrt{npq}+\frac{1}{2}x^2q-x^2q+...\right)+\left(x\sqrt{npq}+\frac{1}{2}x^2p-x^2p-...\right) \right\}\\&=\frac{1}{\sqrt {2\pi npq}}\exp\left\{-\frac{1}{2}x^2q-\frac{1}{2}x^2p-...\right\}\\&=\frac{1}{\sqrt {2\pi npq}}\exp\left\{-\frac{1}{2}x^2(p+q)-...\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}

See also[edit]

  • Poisson distribution is an alternative approximation of the binomial distribution for large values of n.


  1. ^ Walker, Helen M (1985). "De Moivre on the law of normal probability" (PDF). In Smith, David Eugene. A source book in mathematics. Dover. p. 78. ISBN 0-486-64690-4. But altho’ the taking an infinite number of Experiments be not practicable, yet the preceding Conclusions may very well be applied to finite numbers, provided they be great, for Instance, if 3600 Experiments be taken, make n = 3600, hence ½n will be = 1800, and ½√n 30, then the Probability of the Event’s neither appearing oftner than 1830 times, nor more rarely than 1770, will be 0.682688. 
  2. ^ Papoulis, Pillai, "Probability, Random Variables, and Stochastic Processes", 4th Edition
  3. ^ Feller, W. (1968) An Introduction to Probability Theory and Its Applications (Volume 1). Wiley. ISBN 0-471-25708-7. Section VII.3