渐进分析：n 阶置换中轮换数量的对数

· · 算法·理论

问题：

设随机变量 X_n 是从 n 元置换群中所有元素中均匀随机选择一个，其能拆分成的轮换数量。

试对 \mathbb E[\ln X_n] 做渐进分析。

首先需要指出的是 X_n 的概率分布：

\mathbb P[X_n=k]=\frac{1}{n!}\begin{bmatrix} n \\k \end{bmatrix}

这就是第一类 Stirling 数的经典组合意义。

本人掌握的渐进分析方法并不多，如果有更好的处理方法也欢迎指出。

初步处理

一个比较熟知的结论是 \mathbb E[X_n]=H_n（即调和数），不妨考虑对 D_n=\mathbb E[\ln X_n]-\ln \mathbb E[X_n] 进行分析。
根据 Jensen 不等式，我们有 \mathbb E[\ln X_n] \leq \ln \mathbb E[X_n]，所以必然有 D_n \leq 0。如果能证明 D_n 有界，就能直接得到 \mathbb E[\ln X_n] \sim \log \log n。

要进一步分析，可以使用如下公式：

D_n = \int_0^\infty \frac{1}{-t}\left(\binom{\exp(-t/H_n)+n-1}{n} -\text e^{-t}\right) \text dt

证明这个公式并不困难，只需要先将二项式系数用下降幂表示，并用 Stirling 数展开：

\binom{\exp(-t/H_n)+n-1}{n}=\sum_{i=0}^n \frac{1}{n!}\begin{bmatrix} n \\ i \end{bmatrix}\exp\left(-\frac{it}{H_n} \right)

这样原积分就等于

\begin{aligned}\sum_{i=1}^n \frac{1}{n!}\begin{bmatrix} n \\ i \end{bmatrix}\int_0^\infty \frac{\text e^{-it/H_n}-\text e^{-t}}{-t}\text dt &=-\sum_{i=1}^n \frac{1}{n!} \begin{bmatrix} n \\ i \end{bmatrix}\ln \left( \frac{H_n}{i}\right)\\ &=-\ln H_n+\sum_{i=1}^n \frac{\ln i}{n!} \begin{bmatrix} n \\ i \end{bmatrix} \\ &= \mathbb E[\ln X_n]-\ln \mathbb E[X_n] \end{aligned}

至于 D_n 的这个积分表示是以怎样的动机推出，就不在本文中做详细说明了。简单讲就是用一种错误的推导得出后，再返回来证明正确性的。

比之极限为 1！

现在来分析 D_n 这个积分，固定 \epsilon > 0，容易证明其在 (0,\epsilon) 上的积分是有界的（具体可以参考下文的渐进分析）。现在要证明其在 (\epsilon,+\infty) 上积分也是有界的。

而我们只需要证明 I_n 有界即可：

\begin{aligned}I_n &= \int_0^\infty \binom{\exp(-t/H_n)+n-1}{n}\text dt \\ &= H_n\int_0^1 \frac{1}{u}\binom{u+n-1}{n}\text du\end{aligned}

这需要根据 E-M 求和算出带高阶项的 Stirling 渐进（x>0）：

\left( \frac{x}{\text e}\right)^x \sqrt{2\pi x} \leq x! \leq \left( \frac{x}{\text e}\right)^x \sqrt{2\pi x} \left( 1+\frac{1}{11x}\right)

（需要说明的是，E-M 公式算出的 x^{-1} 项系数为 1/12，这里为了保证其大于 x! 而做了调整）

由此能得到（因为 u-1 <0，不能用此近似，先保留其形式）：

\binom{u+n-1}{n} \leq \left( 1 + \frac{1}{11 (u+n-1)} \right)\frac{\left(\frac{u+n-1}{\text e}\right)^{u+n-1}\sqrt{2\pi (u+n-1)}}{\left( \frac{n}{\text e}\right)^n\sqrt{2\pi n} (u-1)!}

化简一下，将其中有界的项都拿出来做一下放缩（可以很宽松），得到：

\binom{u+n-1}{n} \leq 10\frac{(n-1)^{u-1}}{\Gamma(u)}

容易证明对于 u\in (0,1)， u \Gamma (u) \geq 1/2，所以

I_n \leq 20 H _n \int_0^1 (n-1)^{u-1}\text du=\frac{20 H_n (n-2)}{(n-1 )\ln (n-1)}

此时就显然能看出 I_n 是有界的，所以 D_n 也是有界的，所以就有

\lim_{n \to \infty} \frac{\mathbb E[\ln X_n]}{\ln \mathbb E[X_n]} = 1

现在分析出的结果是 \mathbb E[\ln X_n] = \ln H_n + \mathcal O(1)，能不能更进一步呢？

差之极限为 0？

在分析 D_n 这个积分于 n \to \infty 时的情况时，我们很想把积分和极限交换顺序，即考虑分析

\int_0^\infty \frac{1}{(-t)}\left( -\text e^{-t}+\lim_{n \to \infty}\binom{\exp(-t/H_n)+n-1}{n}\right)\text dt

先尝试计算一下交换顺序后的结果，然后再来补一下证明吧。
固定 t，设 a_n=\exp(-t/H_n)-1（别忘记 -1 <a_n\leq 0）：

\lim_{n\to\infty}\binom{a_n+n}{n}= \lim_{n \to \infty} \frac{(a_n+n)!}{a_n!n! }

显然 \lim_{n\to \infty} a_n!=1，然后使用 Stirling 公式来处理同阶无穷大，原极限即为

\lim_{n\to \infty} \frac{\left(\frac{a_n+n}{\text e}\right)^{a_n+n}\sqrt{2\pi (n+a_n)}}{\left( \frac{n}{\text e}\right)^n\sqrt{2\pi n}}=\lim_{n\to\infty} \text e^{-a_n}(a_n+n)^{a_n}\left( \frac{a_n+n}{n}\right)^n

也容易看出 \lim_{n \to \infty} \text e^{-a_n}=1。另一部分可以用取对数再极限的方法来做：

\begin{aligned}\lim_{n \to \infty}\left( \frac{a_n+n}{n}\right)^n&=\exp \lim_{n \to\infty}n \ln \left( 1+\frac{a_n}{n}\right) \\ &=\exp \lim_{n\to \infty} n \left( \frac{a_n}{n}-\frac{a_n^2}{2n^2}+o(a_n^2/n^2)\right) \\ &= 1\end{aligned}

最后就是

\begin{aligned}\lim_{n \to \infty} (a_n + n)^{a_n} &= \lim_{n \to \infty} n^{a_n}\left( 1+\frac{a_n}{n}\right)^{a_n} \\ &= \lim_{n\to \infty} n^{a_n}\end{aligned}

此时可以夹一下，利用 \ln n \leq H_n \leq \ln n + \gamma+1/(2n)，可以算出

\begin{aligned}\lim_{n \to \infty} n^{\exp(-t/(\ln n+c))-1} &=\exp\lim_{n \to \infty}\left( \exp\left(-t\right)^{1/(\ln n +c)}-1\right)\ln n \\ &=\exp \lim_{n \to \infty}n\left( \exp(-t)^{1/n}-1\right)\end{aligned}

极限中就是 \ln 的一种定义，其为 (-t)，所以最终得到

\lim_{n\to\infty}\binom{a_n+n}{n}=\text e^{-t}

这也就是说，如果积分和极限顺序可交换，就能得到

\lim_{n\to\infty}D_n=0

这是比 D_n 有界要强得多的结论。

严谨性的补充？

很遗憾，对于积分和极限能否交换我尚未完成证明。通常用的两种方法无非是 Lebesgue 的两个收敛定理「控制收敛定理」与「单调收敛定理」。
这个问题的结构并不简单，所以我也没有构造出相应的函数来应用此定理。此篇文章仅作抛砖引玉，希望感兴趣的同学可以补充一下证明。

最后就是结论：

已经证明的是 \mathbb E[\ln X_n]\sim\ln H_n。若上文中 D_n 的极限可以与积分交换顺序，则有

\lim_{n \to \infty} (\mathbb E[\ln X_n]-\ln H_n)=0