Stirling’s Approximation

While defining the Gibbs entropy, I quoted an equation called Stirling’s approximation, which says that

\ln n!\approx n\ln n-n

if n is a large number. In this post we’ll discover where this equation comes from.

\

Unfortunately, the method I’m about to show you uses another equation which completely eclipses the result in beauty. It is

\displaystyle n!=\int_0^\infty x^n e^{-x} dx

This expression warrants a discussion of its own, but for now we’ll take it as read. If this equation is unfamiliar to you, take a look at the Gamma function.

The Stirling approximation can be derived by approximating the integrand in the equation above. For shorthand, we’ll name it little gamma:

\gamma (x)=x^n e^{-x}

Before we decide how to approximate this function, let’s work out what it looks like. First of all, we see that

\gamma (0)=\gamma (\infty) = 0

That is, the integrand vanishes at the limits of integration. Why is this? That \gamma goes to 0 at the origin is clear enough, since

\gamma (0) = 0^n\cdot e^0=0\cdot 1 = 0

What about as x tends to infinity? Although x^n blows up quickly, it doesn’t do so quick enough to counteract the crushing force of e^{-x}. The limit

\displaystyle \gamma (\infty)=\lim_{x\to\infty}\Bigg(\frac{x^n}{e^x}\Bigg)

can be formally calculated in a number of ways, the most convincing of which uses l’Hôpital’s rule.

So \gamma starts and ‘ends’ at zero. How does it behave in-between? Let’s look at its derivative:

\displaystyle \frac{d\gamma}{dx}=\frac{d}{dx}(x^n e^{-x})

\displaystyle \frac{d\gamma}{dx}=\frac{d}{dx}(x^n)e^{-x}+x^n\frac{d}{dx}(e^{-x})

\displaystyle \frac{d\gamma}{dx}=nx^{n-1}e^{-x}-x^n e^{-x}

\displaystyle \frac{d\gamma}{dx}=(n-x)x^{n-1} e^{-x}

Note that, like \gamma itself, the gradient of \gamma goes to zero at the limits of integration. More importantly, the first factor tells us that

\displaystyle \frac{d\gamma(n)}{dx}=0

That is, the function has an extremum (which must be a maximum since \gamma \ge 0 for x \ge 0) at x=n. Using what we’ve learnt, we can draw a fairly comprehensive sketch of \gamma. The diagram below shows sketches of \gamma for n=2,3,4.

gammas

The diagram above shows that it would be a good idea to approximate \gamma(x) about the point x=n. We want our expansion of \gamma to be most accurate around its maximum, so that we don’t lose a significant amount of its area when we finally integrate it. With this in mind, let’s write x in the form

x=n+\zeta

The new independent variable \zeta measures how far to the left or right of \gamma‘s maximum we are. So now we have

\gamma=(n+\zeta)^n e^{-(n+\zeta)}

There are far too many powers going on here, so let’s temporarily work with the natural logarithm of \gamma:

\ln\gamma=\ln[(n+\zeta)^n e^{-(n+\zeta)}]

\ln\gamma=\ln(n+\zeta)^n+\ln e^{-(n+\zeta)}

\ln\gamma = n\ln(n+\zeta)-(n+\zeta)

We’re now going to Taylor expand the logarithm on the right-hand side using the equation

\ln(1+x)\approx x-\frac{1}{2}x^2

which is most accurate for small x. To get the logarithm into this form, we’re going to take out a ‘factor’ of n:

\displaystyle \ln\gamma=n\ln\Big(n\Big[1+\frac{\zeta}{n}\Big]\Big)-(n+\zeta)

\displaystyle \ln\gamma=n\ln n+n\ln\Big(1+\frac{\zeta}{n}\Big)-(n+\zeta)

We can now use the Taylor expansion because in the area around \gamma‘s maximum, n is larger than \zeta, hence \frac{\zeta}{n} is ‘small’. So

\displaystyle \ln\gamma\approx n\ln n+n\Big(\frac{\zeta}{n}-\frac{\zeta^2}{2n^2}\Big)-(n+\zeta)

\displaystyle \ln\gamma\approx n\ln n-n-\frac{\zeta^2}{2n^2}

Exponentiating both sides, we find

\displaystyle \gamma=n^n e^{-n} e^{-\frac{\zeta^2}{2n}}

\displaystyle \gamma(x)\approx n^n e^{-n} \exp\Bigg({-\frac{(x-n)^2}{2n}}\Bigg)

So approximately, the integrand is a Gaussian. The diagram below compares our approximation of \gamma to its exact shape for n=15, the former show in brown and the latter in gold.

gamma approximation

Not too bad!

Let’s reconsider the equation for n! given above:

\displaystyle n!=\int_0^\infty x^n e^{-x} dx

Using our expression for the integrand \gamma,

\displaystyle n!\approx n^n e^{-n}\int_{-n}^\infty e^{-\frac{\zeta^2}{2n}}d\zeta

Note that the lower limit of integration has changed, since we’re using the new variable \zeta which is equal to -n when x is zero. One last approximation: we’ve demanded that n is ‘large’, so we’ll extend the lower limit of integration to negative infinity. This doesn’t hurt too much, since the integrand \gamma has all but vanished by the time \zeta reaches -n, so the additional area that will be included is only small. So,

\displaystyle n!\approx n^n e^{-n}\int_{-\infty}^\infty e^{-\frac{\zeta^2}{2n}}d\zeta

The integral is a ‘standard’ one, and evaluation gives

n!\approx n^n e^{-n} \sqrt{2\pi n}

Finally, we take the logarithm of both sides:

\ln n!\approx n\ln n-n+\frac{1}{2}\ln 2\pi n

This method actually gives us an additional term on order of the logarithm of n. This term is often omitted since it increases much more slowly than either n or nln(x) as n increases. Doing so yields the desired result

\ln n!\approx n\ln n - n

Test how good Stirling’s approximation is for a few values of n for yourself. If you want to check really big values of n you’ll have to use something powerful like Mathematica – most handheld calculators conk out at 69!, and both Google and Excel can’t handle anything bigger than 170!.

Return to top

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s