A Probabilistic Proof of Stirling’s Formula

What is Stirling’s formula?

It is familiar that the quantity n! grows very quickly with n. Stirling’s formula gives an approximate value of n! which can be computed more easily and is quite accurate even for small values of n. The formula states that

\displaystyle n!\sim \sqrt{2\pi} e^{-n} n^{n+1/2},

where a_n \sim b_n denotes that \displaystyle \lim_{n\to\infty} a_n/b_n = 1.

Here I am going to discuss a probabilistic proof of Stirling’s formula. The proof is originally due to Rasul A. Khan [2].

Setup of the probabilistic proof

Let X_1, X_2, \dots be i.i.d. (independent and identically distributed) observations from the standard exponential distribution which has mean and variance both equal to 1. Define S_n = \sum_{i=1}^n X_i, for n\geq 1. It is well known that S_n follows \text{Gamma}(n, 1) distribution, which has the density \displaystyle \frac{e^{-x}x^{n-1}}{(n-1)!},\ x>0. We can standardize S_n and define \displaystyle Z_n = \frac{S_n - n}{\sqrt{n}}. Then by the standard Central Limit Theorem (CLT) we have Z_n \stackrel{d}{\rightarrow} Z as n\to\infty, where Z\sim N(0, 1). Here \stackrel{d}{\rightarrow} denotes convergence in distribution.

Connection with Stirling’s formula?

Suprizingly enough, the expected value of |Z_n| relates to the Stirling’s formula. Let us do the calculation ourselves. First note that \displaystyle E|Z_n| = E\left|\frac{S_n-n}{\sqrt{n}}\right|=\int_{0}^\infty \left|\frac{x-n}{\sqrt{n}}\right|\frac{e^{-x}x^{n-1}}{(n-1)!}dx. Substituting u = x/n, it becomes

\displaystyle \frac{n^{n+1/2}}{(n-1)!}\int_{0}^\infty \left|u-1\right|e^{-nu}u^{n-1}du.

Keep aside the constant factor and split the last integral in two parts:

\displaystyle \int_{0}^1 (1-u)e^{-nu}u^{n-1}du+\int_{1}^\infty (u-1)e^{-nu}u^{n-1}du.

Now integrating by parts, we get

\displaystyle \int_0^1 u^{n-1}e^{-nu}du = e^{-nu}\frac{u^n}{n}\Big|_0^1 +\int_0^1 u^n e^{-nu}du

and

\displaystyle \int_1^\infty u^{n-1}e^{-nu}du = e^{-nu}\frac{u^n}{n}\Big|_1^\infty +\int_1^\infty u^n e^{-nu}du.

Observe how it drastically simplifies the required integral and gives

\displaystyle E|Z_n| = \frac{n^{n+1/2}}{(n-1)!}\left( e^{-nu}\frac{u^n}{n}\Big|_0^1 - e^{-nu}\frac{u^n}{n}\Big|_1^\infty\right) = \frac{2e^{-n}n^{n+1/2}}{n!}.

On the other hand,

\displaystyle E|Z| = \int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}}|x|e^{-x^2/2}dx = \sqrt{\frac{2}{\pi}} (check!).

Since Z_n \stackrel{d}{\rightarrow} Z, it is no surprize that E|Z_n| \rightarrow E|Z|, which gives us nothing but the Stirling’s formula.

Are we done yet?

We wrote above that Z_n \stackrel{d}{\rightarrow} Z implies E|Z_n| \rightarrow E|Z|, which actually does not hold in general. However, in this case we are fortunate, because we can apply the following result [1]:

Result: If Z_n \stackrel{d}{\rightarrow} Z as n\to\infty, and if \sup_{n\ge 1} E(Z_n^2) <\infty, then we can conclude that E(Z_n) \rightarrow E(Z) as n\to\infty.

Note that in our case Z_n is the standardized S_n, so E(Z_n^2) = 1 for every n\ge 1. Hence applying the above result to |Z_n| we are through. A proof of the above result can be found here.

References

  1. Billingsley, Patrick. Probability and measure. John Wiley & Sons, 2008.
  2. Khan, Rasul A. “A probabilistic proof of Stirling’s formula.” The American Mathematical Monthly 81.4 (1974): 366-369.

One thought on “A Probabilistic Proof of Stirling’s Formula

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s