Stirling's Approximation

To take a quick detour, let us examine the following definition of the factorial:

\begin{eqnarray}
N! &=& \int_0^\infty x^N e^{-x}dx
\end{eqnarray}

One way to prove this is to write

\begin{eqnarray}
I(a) \int_0^\infty e^{-ax}dx &=& \frac{1}{a}
\end{eqnarray}

and take the derivative underneath the integral sign, to write:

\begin{eqnarray}
I^\prime(a) &=& \frac{\partial}{\partial a} \int_0^\infty e^{-ax}dx \\
&=& \int_0^\infty -ax e^{-ax}dx \\
&=& \frac{-1}{a^2}
\end{eqnarray}

and more generally,

\begin{eqnarray}
\frac{\partial^n I(a)}{\partial a^n} &=& (-1)^n \int_0^\infty a^n x^n e^{-ax}dx = \frac{(-1)^n n!}{a^{n+1}}
\end{eqnarray}

Setting $a=1$ we find

\begin{eqnarray}
\Gamma[n+1] &=& \int_0^\infty x^n e^{-x}dx =  n!
\end{eqnarray}

Now let's examine this integral in the limit $n \to \infty$. We can take our $x$ argument up, into the exponential and write the corresponding function as $f(x)$:

\begin{eqnarray}
n! &=& \int_0^\infty e^{-x+n \log x}dx\\
&=& \int_0^\infty e^{f(x)}dx\\
f(x) &=& -x + n \log x
\end{eqnarray}

Now $f(x)$ is an absurdly large -- or high-valued -- function for large $n$, and so we can approximate this integral as only "counting" contributions around the maximum of $f(x)$. We find the position this maximum in the normal way:

\begin{eqnarray}
f^\prime &=& -1 + \frac{n}{x} = 0 \\
x_0 &=& n
\end{eqnarray}

Taking a look at our second derivative
\begin{eqnarray}
f^{\prime \prime}\vert_{x_0} &=& -\frac{n}{x^2} = -\frac{1}{n} < 0
\end{eqnarray}

we see that $x_0$ is the position of a true maximum. Expanding out our $f(x)$ with a Taylor approximation:

\begin{eqnarray}
n! &\approx& \int_0^\infty e^{f(x_0)+f^\prime(x) \vert_{x_0}(x-x_0)+f^{\prime \prime}(x) \vert_{x_0}\frac{(x-x_0)^2}{2}}dx\\
\end{eqnarray}

We see that the first derivative term is zero by construction, and we are left with a constant times a Gaussian,

\begin{eqnarray}
n! &\approx& e^{-n+n\log n}\int_0^\infty e^{\frac{(x-x_0)^2}{2n}}dx\\
&\approx& n^n e^{-n}\int_0^\infty e^{\frac{(x-n)^2}{2n}}dx\\
\end{eqnarray}

Now this integral is tricky, because we are taking the limit as $n \to \infty$, which means that, essentially, the middle of our Gaussian distribution is far afield from $x=0$. Since the integral of any Gaussian $e^{-x^2/(2\sigma^2)}$ is $\sqrt{2 \pi \sigma^2}$, we can approximate the integral above to be the "full" $-\infty < x < \infty$ integration, because our moment, or center of the distribution, $x_0$ is far to the positive side of zero. This yields, with $\sigma^2=\sqrt{n}$:

\begin{eqnarray}
n! &\approx& n^n e^{-n}\sqrt{2\pi n}
\end{eqnarray}

Which is stirling's approximation!

Now if we use this approximation to examine the binomial distribution in the same limit:

\begin{eqnarray}
P(k;N) &=& \frac{N!}{k! (N-k)!}p^k (1-p)^{N-k}
\end{eqnarray}