从零推导斯特林公式

  |  

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

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


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

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

另外 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!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:

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

面积原理,$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})$ 成立。

同时积分,得到以下不等式:

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

分部积分

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

令 $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$:

于是,$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)!!$

于是得到结果如下

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

化简后得到:

于是通过夹逼定理即可得到我们要证明的 $\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$

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

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


Share