Monday Math 124

The central limit theorem tells us that for sufficiently large n, the mean of n samples of any random variable for which the first and second moments (and thus mean and variance) exist has a distribution that approaches, and can thus be approximated by, a normal distribution (Gaussian distribution).

Now, consider the case of the probability of getting exactly k heads in n (fair) coin flips. This is described by the binomial distribution with p=q=1/2
$P(K=k)=\left({{n}\atop{k}}\right)\left(\frac{1}{2}\right)^k\left(1-\frac{1}{2}\right)^{n-k}=\frac{1}{2^n}\left({{n}\atop{k}}\right)$ ,
where
$\left({{n}\atop{k}}\right)=\frac{(n)!}{k!(n-k)!}$ .
The mean is $\frac{n}2$ .

Now, suppose we have 2n flips (so that the mean is n), and we consider the probability of getting $k=n+x$ heads (so that x is the difference from the mean). What is the Gaussian approximation for the probability distribution when n is large, and what are the limits on x for which the approximation is valid?

From our binomial distribution, we have
$P(x)=\frac{1}{2^{2n}}\left({{2n}\atop{n+x}}\right)$
and
$\left({{2n}\atop{n+x}}\right)=\frac{(2n)!}{(n+x)!(n-x)!}$ .
Now, recall Stirling’s approximation
$n!\approx{n^n}e^{-n}\sqrt{2\pi{n}}$
for large n. Then
$(2n)!\approx{(2n)^{2n}}e^{-2n}\sqrt{4\pi{n}}$
$(n+x)!\approx{(n+x)^{n+x}}e^{-(n+x)}\sqrt{2\pi(n+x)}$
and
$(n-x)!\approx{(n-x)^{n-x}}e^{-(n-x)}\sqrt{2\pi(n-x)}$
so
$\begin{eqnarray}\left({{2n}\atop{n+x}}\right)&=&\frac{(2n)!}{(n+x)!(n-x)!}\\&\approx&\frac{(2n)^{2n}e^{-2n}\sqrt{4\pi{n}}}{(n+x)^{n+x}e^{-(n+x)}\sqrt{2\pi(n+x)}(n-x)^{n-x}e^{-(n-x)}\sqrt{2\pi(n-x)}}\\&\approx&\frac{(2n)^{2n}\sqrt{n}}{(n+x)^{n+x}(n-x)^{n-x}\sqrt{\pi}\sqrt{n^2-x^2}}\\&\approx&\frac{2^{2n}\sqrt{n}}{\left(1+\frac{x}n\right)^{n+x}\left(1-\frac{x}n\right)^{n-x}\sqrt{\pi}\sqrt{n^2-x^2}}\end{eqnarray}$

Now, to approximate the $\left(1+\frac{x}n\right)^{n+x}$ and $\left(1-\frac{x}n\right)^{n-x}$ terms, we use
$\left(1+\frac{x}n\right)^{n+x}=e^{(n+x)\ln\left(1+\frac{x}n\right)}$ .
Now, we expand to second order in the exponent by expanding the logarithm via the Mercator series:
$\begin{eqnarray}\left(1+\frac{x}n\right)^{n+x}&=&e^{(n+x)\ln\left(1+\frac{x}n\right)}\\&=&e^{(n+x)\left(\frac{x}n-\frac{x^2}{2n^2}+\cdots\right)}\\&\approx&e^{x+\frac{x^2}{2n}}\end{eqnarray}$ ,
and $x\to-x$ gives us
$\left(1-\frac{x}n\right)^{n-x}\approx{e}^{-x+\frac{x^2}{2n}}$ .
Substituting these into our approximation of the binomial coefficient,
$\begin{eqnarray}\left({{2n}\atop{n+x}}\right)&\approx&\frac{2^{2n}\sqrt{n}}{\left(1+\frac{x}n\right)^{n+x}\left(1-\frac{x}n\right)^{n-x}\sqrt{\pi}\sqrt{n^2-x^2}}\\&\approx&\frac{2^{2n}\sqrt{n}}{e^{x+\frac{x^2}{2n}}e^{-x+\frac{x^2}{2n}}sqrt{\pi}\sqrt{n^2-x^2}}\\&\approx&\frac{2^{2n}\sqrt{n}e^{-\frac{x^2}{n}}}{sqrt{\pi}\sqrt{n^2-x^2}}\end{eqnarray}$ .
The exponential tells us that only x up to order $\sqrt{n}$ have a significant contribution, so we can use $\sqrt{n^2-x^2}\approx{n}$ , obtaining
$\left({{2n}\atop{n+x}}\right)\approx\frac{2^{2n}e^{-\frac{x^2}{n}}}{sqrt{\pi{n}}}$ ,
and so
$P(x)\approx\frac{e^{-\frac{x^2}{n}}}{sqrt{\pi{n}}}$ .
Note that since $\int_{-\infty}^{\infty}e^{-x^2/n}dx=\sqrt{\pi{n}}$ , the above Gaussian distribution does integrate to unity, as expected of a proper distribution.
To test the validity of this approximation, let us expand the exponents in the $\left(1+\frac{x}n\right)^{n+x}$ and $\left(1-\frac{x}n\right)^{n-x}$ terms to fourth order (third order terms, like the first order terms, will cancel):
$\begin{eqnarray}\left(1+\frac{x}n\right)^{n+x}&=&e^{(n+x)\ln\left(1+\frac{x}n\right)}\\&=&e^{(n+x)\left(\frac{x}n-\frac{x^2}{2n^2}+\frac{x^3}{3n^3}-\frac{x^4}{4n^4}+\cdots\right)}\\&\approx&e^{x+\frac{x^2}{2n}-\frac{x^3}{6n^2}+\frac{x^4}{12n^3}}\end{eqnarray}$ ,
and
$\left(1-\frac{x}n\right)^{n-x}\approx{e}^{-x+\frac{x^2}{2n}+\frac{x^3}{6n^2}+\frac{x^4}{12n^3}}$ ,
so we now get
$\begin{eqnarray}\left({{2n}\atop{n+x}}\right)&\approx&\frac{2^{2n}}{e^{x+\frac{x^2}{2n}-\frac{x^3}{6n^2}+\frac{x^4}{12n^3}}e^{-x+\frac{x^2}{2n}+\frac{x^3}{6n^2}+\frac{x^4}{12n^3}}sqrt{\pi{n}}}\\&\approx&\frac{2^{2n}e^{-\frac{x^2}{n}}e^{-\frac{x^4}{6n^3}}}{sqrt{\pi{n}}}\end{eqnarray}$ .
and so
$P(x)\approx\frac{e^{-\frac{x^2}{n}}}{sqrt{\pi{n}}}e^{-\frac{x^4}{6n^3}}$ ;
this correction term $e^{-\frac{x^4}{6n^3}}$ differs significantly from unity only when x approaches the order of $n^{3/4}$ ; at that point, however, the probability is already negligibly small for large n ( $e^{-\frac{x^2}{n}}\sim{e}^{-\sqrt{n}}$ ).

Like this:

Be the first to like this post.

Tags: Binomial Distribution, Gaussian, Gaussian Integral, Math, Monday Math, Stirling's Approximation

This entry was posted on June 21, 2010 at 12:07 am and is filed under Math/Science. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Monday Math 124”

Monday Math 125 « Twisted One 151's Weblog Says:
June 28, 2010 at 12:24 am | Reply
[...] value is thus . For large N, we can approximate our binomial coefficient with a Gaussian; from this previous post, we found (where for convienience, we have renamed one of the variables). To express our above [...]

Twisted One 151's Weblog

Monday Math 124

Like this:

One Response to “Monday Math 124”

Leave a Reply Cancel reply

Follow “Twisted One 151's Weblog”