假设口袋里有 100 根绳子，随机从里面抽出两个头打个结再放回去，直到没有空闲的绳头为止。最后得到的圈数的期望值是多少？
这个问题乍看起来就和这一口袋绳子一样毫无头绪。随机打结可能会恰好把一根绳子打成结，也可能把两根绳子连在了一起，但是在若干步之后又恰好把这两根绳子的另一头扎起来了……
还是一步一步来分析一下吧。比方说一开始有 \(n\) 根绳子，那就有 \(2n\) 个绳头。如果随便拿出两个绳头来打结，那就有如下几种可能：
- 恰好抽到了一根绳子的两个头，打结之后这根绳子就再也不用考虑了。这时我们还剩下 \(n-1\) 根绳子，和 \(2(n-1)\) 个绳头。这时就多了一个圈。
- 抽到的两个头不是一根绳子的，打结之后，两根绳子就变成了一根，绳头也少了两个。于是我们还是剩下 \(n-1\) 根绳子，和 \(2(n-1)\) 个绳头。这时没有多出圈来。
从 \(2n\) 个绳头里面挑出两个头，共有 \(\binom{2n}{2}\) 种挑法，其中 \(n\) 种情况会挑到一根绳子的两个头。于是多出来一个圈的概率就是
\[
\displaystyle \frac{n}{\binom{2n}{2}} = \frac{n}{\frac{2n(2n-1)}{2}}=\frac{1}{2n-1}.
\]
这时候还剩下 \(n-1\) 根绳子。以此类推，一直到剩下一根绳子，所以最后得到的圈数的期望就是
\[
\displaystyle \frac{1}{2n-1} + \frac{1}{2n-3} + \frac{1}{2n-5} + \cdots + \frac{1}{3} + 1.
\]
这问题似乎就算解决了……似乎。可这个数算出来是多少呢？
编个程序算一下，这个结果是 3.2843。想想 100 根绳子忙到最后，平均才只能得到 3 个圈，这个机会真是不大。
再来观察一下这个级数，我们知道调和数
\[
\displaystyle H_n= 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} =\sum_{k=1}^n \frac{1}{k}.
\]
那么
\[
\begin{aligned}
&\displaystyle \frac{1}{2n-1} + \frac{1}{2n-3} + \frac{1}{2n-5} + \cdots + \frac{1}{3} + 1\\
=&\displaystyle \left( \frac{1}{2n} + \frac{1}{2n-1} + \frac{1}{2n-2} + \cdots + \frac{1}{2} + 1 \right) – \left( \frac{1}{2n} + \frac{1}{2n-2} + \frac{1}{2n-4} + \cdots + \frac{1}{2} \right)\\
=&H_{2n} – \frac{1}{2}H_n\end{aligned}
\]
我们可以用 Mathematica 来算这个HarmonicNumber[200]- HarmonicNumber[100]/2，得到了精确解……@_@
\[
\displaystyle \frac{8654590343632330736271597329038616601268156410349231938070835683330531233950965153947472}{2635106162757236442495826303084698495565581115509040892412867358728390766099042109898375}.
\]
调和数有一个渐进形式：
\[
\displaystyle H_n \sim \ln n+ \gamma + \frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120 n^4}-\frac{1}{252n^6}+\cdots,
\]
其中 \(\gamma= 0.5772156649\cdots\) 是欧拉常数。于是
\[
H_{2n} – \frac{1}{2}H_n \sim \ln 2 + \frac{1}{2}\ln n + \frac{1}{2} \gamma + O(n^{-2}) \approx \frac{1}{2}\ln n + 0.9818.
\]
所以，圈数的期望的增长正比于绳数的对数。那么这样算下来，10000 根绳子得到的圈数的期望也不不过是 5.587……这个活动是有多么悲催…… -_-|||