Stirling's Approximation

Stirling’s Approximation

Stirling’s approximation, which states that \(\Gamma(n+1) \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n\) as \(n \to \infty\), is useful when estimating the order of \(n!\). Notably, it is quite accurate even when \(n\) is small.

The authentic proof entails Gamma function and Laplace’s method. However in integer case, Stirling’s approximation can be approached with Poisson distribution. Start from a Poisson distribution with mean \(\lambda\): \[ P(r ; \lambda) = e^{-\lambda} \frac{\lambda^r}{r!} \] When \(X \sim P(\lambda_1)\), \(Y \sim P(\lambda_2)\), and suppose \(X\) and \(Y\) are independent, \(X + Y \sim P(\lambda_1 + \lambda_2)\).

• Proof \[ \begin{aligned} & \Pr(X + Y = r) = \sum_{k=0}^r \Pr(X = k) \Pr(Y = r-k) \\ &= \sum_{k=0}^r e^{-\lambda_1} \frac{\lambda_1^k}{k!} e^{-\lambda_2} \frac{\lambda_2^{r-k}}{(r-k)!} \\ &= \frac{e^{-(\lambda_1 + \lambda_2)}}{r!} \sum_{k=0}^r \frac{r!}{k! (r-k)!} \lambda_1^k \lambda_2^{r-k} \\ &= e^{-(\lambda_1 + \lambda_2)} \frac{(\lambda_1 + \lambda_2)^r}{r!} \\ &= P(r; \lambda_1 + \lambda_2) \end{aligned} \]

Therefore, a random variable \(X \sim P(\lambda)\) (with integer \(\lambda\)) can be treated as the addition of \(\lambda\) independent \(Y_i \sim P(1)\). By the central limit theorem, for a large \(\lambda\), \[ \mathbb \Pr(\frac{\underbrace{\sum_i Y_i}_X - \lambda}{\sqrt{\lambda}} \le x) \simeq \Phi(x) \] Or put it another way, the mass of the Poisson distribution \(X\) follows is well approximated by the density of the Gaussian distribution with mean \(\lambda\) and variance \(\lambda\): \[ \begin{aligned} P(x;\lambda) &\simeq N(x; \lambda, \lambda) \\ e^{-r} \frac{\lambda^r}{r!} &\approx \frac{1}{\sqrt{2\pi \lambda}} e^{-\frac{(r - \lambda)^2}{2\lambda}} \end{aligned} \] Plug \(r = \lambda\) into this formula and rearrange it to have \[ \begin{aligned} e^{-\lambda} \frac{\lambda^\lambda}{\lambda!} &\approx \frac{1}{\sqrt{2\pi \lambda}} \\ \lambda! &\approx \sqrt{2\pi \lambda} \left( \frac{\lambda}{e} \right)^\lambda \end{aligned} \]