随机打结意大利面：形成环的期望个数

Randomly tying spaghetti ends, expected number of loops

专题: Probability / 概率
难度: L6
来源: QuantQuestion

题目详情

碗里有多根意大利面（每根有两个自由端）。每次随机选取两个自由端并把它们打结连接。最终会形成若干个闭环。

问：平均会形成多少个闭环？（用意大利面条数 $n$ 表示）

You have multiple strands of spaghetti in a bowl. Each time, pick two free ends at random and tie them together. Eventually you get loops. On average, how many loops do you form?

解析

设共有 $n$ 根意大利面（共 $2n$ 个端点）。一个经典结果是：最终闭环数的期望为

\mathbb{E}[\#\text{loops}]=1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2n-1}=\sum_{k=1}^{n}\frac{1}{2k-1}.

直观解释：在随机配对端点的过程中，“新打结恰好闭合一个环”的概率随着当前连通分量的结构变化，但期望可以用线性性与对称性归纳得到上述奇数调和和。