从零推导斯特林公式

摘要: 本文从零推导信息论、热力学、机器学习中经常用到的斯特林公式。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

算法工程师应该对信息论都比较熟，很多loss函数都是基于信息论的。信息论中关于采样定理、二分分布的极限分布等关键结论的推导过程都用到了斯特林（Stirling）公式。

在热力学中推导平衡状态下的气体分子的能量分布函数，需要用到斯特林公式，与二项分布的极限分布殊途同归。

另外 SVM 中的 RBF 核中有一个 $\Gamma$ 函数，它的推导也用到了斯特林公式。

本文我们就从零推导这个隐藏在幕后的斯特林公式。公式如下：

$$\lim\limits_{n \rightarrow \infty} \frac{n!}{(\frac{n}{e})^{n}\sqrt{2\pi n}} = 1$$

虽然叫从零推导，有一些结论我们还是直接承认的，不然就太长了。

• 单调有界定理
• 面积原理
• 夹逼定理
• 分部积分法

这四个结论我们在推导过程图中会不加证明地使用，具体内容在用到的位置会展开。

---

证明过程

要证明 $\lim\limits_{n \rightarrow \infty} \frac{n!}{(\frac{n}{e})^{n}\sqrt{2\pi n}} = 1$，即要证明 $\lim\limits_{n \rightarrow \infty} \frac{n!e^{n}}{n^{n+\frac{1}{2}}} = \sqrt{2\pi}$。

令 $a_{n}=\frac{n!e^{n}}{n^{n+\frac{1}{2}}}$，下面我们证明 $\lim\limits_{n \rightarrow \infty}a_{n} = \sqrt{2\pi}$。

证明过程分为两步，第一步是证明该极限存在，第二步是证明该极限为 $\sqrt{2\pi}$。

在证明该极限存在这一步，我们首先证明 $a_{n}$ 单调，再证明 $a_{n}$ 有界，根据单调有界定理我们就证明了极限 $\lim\limits_{n \rightarrow \infty}a_{n}$ 存在。

单调有界定理

单调有界数列一定有极限

有界比较容易，$a_{n} > 0$，单调比较难，下面我们证明 $a_{n}$ 单调递减。

要证明 $a_{n}$ 单调递减，只需要证明 $\frac{a_{n}}{a_{n+1}} > 1$ 即可。

也就是要证明 $(1+\frac{1}{n})^{n+\frac{1}{2}}\frac{1}{e} > 1$

两边取对数，也就是要证明 $\frac{1}{n+\frac{1}{2}} < \ln(1+\frac{1}{n})$

考虑函数 $y = \ln x$ 在 a 到 b 之间的面积。有两种计算方式：

第一种是用积分计算，结果记为 A：

$$A = \int^{b}_{a}\ln xdx = x(\ln x - 1)|^{b}_{a} = b\ln b - a\ln a + a - b$$

第二种是用内接梯形面积近似，结果记为 B：

$$B = \frac{1}{2}(\ln b + \ln a)(b - a)$$

由面积原理，$B < A$，化简后得到 $\frac{2}{a + b} < \frac{\ln b - \ln a}{b-a}$

面积原理

若 $x \geq m \in N^{*}$ 时，f 是非负递增函数
则当 $\xi \geq m$ 时，有
$\left|\sum\limits_{k=m}\limits^{[\xi]}f(k) - \int^{\xi}_{m}f(x)dx\right| \leq f(\xi)$

取 a = n，b = n + 1，即可得到 $\frac{1}{n+\frac{1}{2}} < \ln(1+\frac{1}{n})$。

至此我们证明了 $a_{n}$ 单调有界，因此 $\lim\limits_{n \rightarrow \infty}a_{n} = \alpha$ 存在。下面证明 $\alpha = \sqrt{2\pi}$。

由于 $a_{n}=\frac{n!e^{n}}{n^{n+\frac{1}{2}}}$，所以 $\frac{a_{n}^{2}}{a_{2n}} = \frac{(n!)^{2}2^{2n}\sqrt{2}}{(2n)!\sqrt{n}}$。$\lim\limits_{n \rightarrow \infty}\frac{a_{n}^{2}}{a_{2n}} = \frac{\alpha^{2}}{\alpha} = \alpha$。

只要我们能证明 $\lim\limits_{n \rightarrow \infty}\frac{a_{n}^{2}}{a_{2n}} = \lim\limits_{n \rightarrow \infty}\frac{(n!)^{2}2^{2n}\sqrt{2}}{(2n)!\sqrt{n}} = \sqrt{2\pi}$，那么我们就证明了 $\alpha = \sqrt{2\pi}$。

下面我们证明 $\lim\limits_{n \rightarrow \infty}\frac{(n!)^{2}2^{2n}\sqrt{2}}{(2n)!\sqrt{n}} = \sqrt{2\pi}$。

考虑函数 $y = \sin x$，当 $x \in (0, \frac{\pi}{2})$ 时，$0 < sin x < 1$。因此对于 $n \in N^{*}$，以下不等式对于 $x \in (0, \frac{\pi}{2})$ 成立。

$$\sin^{2n+1}x < \sin^{2n}x < \sin^{2n-1}x$$

同时积分，得到以下不等式：

$$\int^{\frac{\pi}{2}}_{0}\sin^{2n+1}xdx < \int^{\frac{\pi}{2}}_{0}\sin^{2n}xdx < \int^{\frac{\pi}{2}}_{0}\sin^{2n-1}xdx$$ 下面用分部积分来求解 $\int^{\frac{\pi}{2}}_{0}\sin^{2n}xdx$ 这个积分。

分部积分

对 $udv = d(uv) - vdu$ 两端积分，得到以下公式

$$\int^{b}_{a}u(x)v'(x)dx = u(x)v(x)\bigg|^{b}_{a} - \int^{b}_{a}v(x)u'(x)dx$$

令 $I_{m} = \int^{\frac{\pi}{2}}_{0}\sin^{m}xdx = \int^{\frac{\pi}{2}}_{0}\cos^{m}xdx$，$m=0,1,2,…$

前两项可以直接算出：$I_{0} = \frac{\pi}{2}$，$I_{1} = 1$。

对于 $m \geq 2$：

$$\begin{align} I_{m} &= \int^{\frac{\pi}{2}}_{0}\cos^{m}xdx = \int^{\frac{\pi}{2}}_{0}\cos^{m-1}xd\sin x \\ &= \cos^{m-1}x\sin x\bigg|^{\frac{\pi}{2}}_{0} + (m-1)\int^{\frac{\pi}{2}}_{0}\cos^{m-2}x\sin^{2}xdx \\ &= (m-1)\int^{\frac{\pi}{2}}_{0}\cos^{m-2}x(1 - \cos^{2}x)dx \\ &= (m-1)I_{m-2} - (m-1)I_{m} \end{align}$$

于是，$I_{m} = \frac{m-1}{m}I_{m-2}$，$m \geq 2$。

记 $1\times 3\times 5 \times … \times (2n-1) = (2n-1)!!$；$2\times 4\times 6 \times … \times (2n) = (2n)!!$

于是得到结果如下

$$I_{2n-1} = \frac{(2n-2)!!}{(2n-1)!!} \quad\quad n=1,2,3,... \\ I_{2n} = \frac{(2n-1)!!}{(2n)!!}\frac{\pi}{2} \quad\quad n=1,2,3,... \\$$

以上就是 $\int^{\frac{\pi}{2}}_{0}\sin^{m}xdx$ 的结果，将 2n+1, 2n, 2n-1 分别代入 m，于是我们的不等式可以写为：

$$\frac{(2n)!!}{(2n+1)!!} < \frac{(2n-1)!!}{(2n)!!}\frac{\pi}{2} < \frac{(2n-2)!!}{(2n-1)!!}$$

化简后得到：

$$(\frac{2n}{2n+1})\frac{\pi}{2} < \frac{((2n)!!)^{2}}{(2n+1)((2n-1)!!)^{2}} < \frac{\pi}{2}$$

于是通过夹逼定理即可得到我们要证明的 $\lim\limits_{n \rightarrow \infty}\frac{(n!)^{2}2^{2n}\sqrt{2}}{(2n)!\sqrt{n}} = \sqrt{2\pi}$。

夹逼定理

设 $a_{n} \leq b_{n} \leq c_{n}$, $n \in N^{*}$，且 $\lim\limits_{n\rightarrow\infty}a_{n} = \lim\limits_{n\rightarrow\infty}c_{n} = a$
那么，$\lim\limits_{n\rightarrow\infty}b_{n} = a$

$$\lim\limits_{n\rightarrow \infty}\frac{((2n)!!)^{2}}{(2n+1)((2n-1)!!)^{2}} = \frac{\pi}{2}$$

化简后即可得到另一写法：

$$\lim\limits_{n\rightarrow \infty}\frac{(n!)^{2}2^{2n}}{(2n)!\sqrt{n}} = \sqrt{\pi}$$

这正是我们要证明的 $\alpha = \sqrt{2\pi}$

---