De Moivre–Laplace theorem

De Moivre–Laplace theorem   (Redirected from Theorem of de Moivre–Laplace) Jump to navigation Jump to search Within a system whose bins are filled according to the binomial distribution (such as Galton's "bean machine", shown here), given a sufficient number of trials (here the rows of pins, each of which causes a dropped "bean" to fall toward the left or right), a shape representing the probability distribution of k successes in n trials (see bottom of Fig. 7) matches approximately the Gaussian distribution with mean np and variance np(1−p), assuming the trials are independent and successes occur with probability p. Consider tossing a set of n coins a very large number of times and counting the number of "heads" that result each time. The possible number of heads on each toss, k, runs from 0 to n along the horizontal axis, while the vertical axis represents the relative frequency of occurrence of the outcome k heads. The height of each dot is thus the probability of observing k heads when tossing n coins (a binomial distribution based on n trials). According to the de Moivre–Laplace theorem, as n grows large, the shape of the discrete distribution converges to the continuous Gaussian curve of the normal distribution.

In probability theory, 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. In particular, the theorem shows that the probability mass function of the random number of "successes" observed in a series of {displaystyle n} independent Bernoulli trials, each having probability {displaystyle p} of success (a binomial distribution with {displaystyle n} trials), converges to the probability density function of the normal distribution with mean {displaystyle np} and standard deviation {textstyle {sqrt {np(1-p)}}} , as {displaystyle n} grows large, assuming {displaystyle p} is not {displaystyle 0} or {displaystyle 1} .

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.[1] This is one derivation of the particular Gaussian function used in the normal distribution.

It is a special case of the central limit theorem because a Bernoulli process can be thought of as the drawing of independent random variables from a bimodal discrete distribution with non-zero probability only for values 0 and 1. In this case, the binomial distribution models the number of successes (i.e., the number of 1s), whereas the central limit theorem states that, given sufficiently large n, the distribution of the sample means will be approximately normal. However, because in this case the fraction of successes (i.e., the number of 1s divided by the number of trials, n) is equal to the sample mean, the distribution of the fractions of successes (described by the binomial distribution divided by the constant n) and the distribution of the sample means (approximately normal with large n due to the central limit theorem) are equivalent.

Contents 1 Theorem 1.1 Proof 1.2 Alternate proof 2 See also 3 Notes Theorem As n grows large, for k in the neighborhood of np we can approximate[2][3] {displaystyle {n choose k},p^{k}q^{n-k}simeq {frac {1}{sqrt {2pi 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: {displaystyle left(X!,-!,npright)!/!{sqrt {npq}}} , with {displaystyle textstyle X} a binomially distributed random variable, approaches the standard normal as {displaystyle n!to !infty } , with the ratio of the probability mass of {displaystyle X} to the limiting normal density being 1. This can be shown for an arbitrary nonzero and finite point {displaystyle c} . On the unscaled curve for {displaystyle X} , this would be a point {displaystyle k} given by {displaystyle k=np+c{sqrt {npq}}} For example, with {displaystyle c} at 3, {displaystyle k} stays 3 standard deviations from the mean in the unscaled curve.

The normal distribution with mean {displaystyle mu } and standard deviation {displaystyle sigma } is defined by the differential equation (DE) {displaystyle f'!(x)!=!-!,{frac {x-mu }{sigma ^{2}}}f(x)} with an initial condition set by the probability axiom {displaystyle 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, {displaystyle textstyle p(k!+!1)!-!p(k)} , the change for step size 1. As {displaystyle textstyle n!to !infty } , the discrete derivative becomes the continuous derivative. Hence the proof need show only that, for the unscaled binomial distribution, {displaystyle {frac {f'!(x)}{f!(x)}}!cdot !left(-{frac {sigma ^{2}}{x-mu }}right)!to !1} as {displaystyle n!to !infty } .

The required result can be shown directly: {displaystyle {begin{aligned}{frac {f'!(x)}{f!(x)}}{frac {npq}{np!,-!,k}}!&={frac {pleft(n,k+1right)-pleft(n,kright)}{pleft(n,kright)}}{frac {sqrt {npq}}{-c}}\&={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 1end{aligned}}} The last holds because the term {displaystyle -cnpq} dominates both the denominator and the numerator as {displaystyle n!to !infty } .

As {displaystyle textstyle k} takes just integral values, the constant {displaystyle textstyle c} is subject to a rounding error. However, the maximum of this error, {displaystyle textstyle {0.5}/!{sqrt {npq}}} , is a vanishing value.[4] Alternate 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 {displaystyle n!simeq n^{n}e^{-n}{sqrt {2pi n}}qquad {text{as }}nto infty .} Thus {displaystyle {begin{aligned}{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 {2pi n}}}{k^{k}e^{-k}{sqrt {2pi k}}(n-k)^{n-k}e^{-(n-k)}{sqrt {2pi (n-k)}}}}p^{k}q^{n-k}\&={sqrt {frac {n}{2pi kleft(n-kright)}}}{frac {n^{n}}{k^{k}left(n-kright)^{n-k}}}p^{k}q^{n-k}\&={sqrt {frac {n}{2pi kleft(n-kright)}}}left({frac {np}{k}}right)^{k}left({frac {nq}{n-k}}right)^{n-k}end{aligned}}} Next, the approximation {displaystyle {tfrac {k}{n}}to p} is used to match the root above to the desired root on the right-hand side.

{displaystyle {begin{aligned}{n choose k}p^{k}q^{n-k}&simeq {sqrt {frac {1}{2pi 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 {2pi npq}}}left({frac {np}{k}}right)^{k}left({frac {nq}{n-k}}right)^{n-k}qquad p+q=1\end{aligned}}} Finally, the expression is rewritten as an exponential and the Taylor Series approximation for ln(1+x) is used: {displaystyle ln left(1+xright)simeq x-{frac {x^{2}}{2}}+{frac {x^{3}}{3}}-cdots } Then {displaystyle {begin{aligned}{n choose k}p^{k}q^{n-k}&simeq {frac {1}{sqrt {2pi 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 {2pi npq}}}exp left{-kln left({frac {k}{np}}right)+(k-n)ln left({frac {n-k}{nq}}right)right}\&={frac {1}{sqrt {2pi npq}}}exp left{-kln left({frac {np+x{sqrt {npq}}}{np}}right)+(k-n)ln left({frac {n-np-x{sqrt {npq}}}{nq}}right)right}\&={frac {1}{sqrt {2pi npq}}}exp left{-kln 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 {2pi npq}}}exp left{-kleft({x{sqrt {frac {q}{np}}}}-{frac {x^{2}q}{2np}}+cdots right)+(k-n)left({-x{sqrt {frac {p}{nq}}}-{frac {x^{2}p}{2nq}}}-cdots right)right}\&={frac {1}{sqrt {2pi npq}}}exp left{left(-np-x{sqrt {npq}}right)left({x{sqrt {frac {q}{np}}}}-{frac {x^{2}q}{2np}}+cdots right)+left(np+x{sqrt {npq}}-nright)left(-x{sqrt {frac {p}{nq}}}-{frac {x^{2}p}{2nq}}-cdots right)right}\&={frac {1}{sqrt {2pi npq}}}exp left{left(-np-x{sqrt {npq}}right)left(x{sqrt {frac {q}{np}}}-{frac {x^{2}q}{2np}}+cdots right)-left(nq-x{sqrt {npq}}right)left(-x{sqrt {frac {p}{nq}}}-{frac {x^{2}p}{2nq}}-cdots right)right}\&={frac {1}{sqrt {2pi npq}}}exp left{left(-x{sqrt {npq}}+{frac {1}{2}}x^{2}q-x^{2}q+cdots right)+left(x{sqrt {npq}}+{frac {1}{2}}x^{2}p-x^{2}p-cdots right)right}\&={frac {1}{sqrt {2pi npq}}}exp left{-{frac {1}{2}}x^{2}q-{frac {1}{2}}x^{2}p-cdots right}\&={frac {1}{sqrt {2pi npq}}}exp left{-{frac {1}{2}}x^{2}(p+q)-cdots right}\&simeq {frac {1}{sqrt {2pi npq}}}exp left{-{frac {1}{2}}x^{2}right}\&={frac {1}{sqrt {2pi npq}}}e^{frac {-(k-np)^{2}}{2npq}}\end{aligned}}} Each " {displaystyle 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 → ∞.

See also Poisson distribution is an alternative approximation of the binomial distribution for large values of n. Notes ^ Walker, Helen M (1985). "De Moivre on the law of normal probability" (PDF). In Smith, David Eugene (ed.). 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. ^ Papoulis, Athanasios; Pillai, S. Unnikrishna (2002). Probability, Random Variables, and Stochastic Processes (4th ed.). Boston: McGraw-Hill. ISBN 0-07-122661-3. ^ Feller, W. (1968). An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley. Section VII.3. ISBN 0-471-25708-7. ^ Thamattoor, Ajoy (2018). "Normal limit of the binomial via the discrete derivative". The College Mathematics Journal. 49 (3): 216–217. doi:10.1080/07468342.2018.1440872. S2CID 125977913. Categories: Central limit theorem