面条打结成环
The Noodles
题目详情
碗里有 100 根面条，每根面条有两个端点。你反复执行：等概率随机选取两个“自由端点”并把它们连接起来，直到没有自由端点。
- 期望会形成多少个闭环？
- 形成一个包含所有面条的“单一大环”的概率是多少？
提示：期望可用线性性；概率可用独立事件连乘。
You have 100 noodles in your soup bowl. You are told to take two ends of some noodles (each end on any noodle has the same probability of being chosen) in your bowl and connect them. You continue until there are no free ends. What is the expected number of loops? What is the probability of making one large loop which includes every noodle?
Hint
Expected number of noodles come from linearity of expectation. Probability comes from multiplying independent probabilities.
解析
- 期望闭环数为
直观做法：把每次“某条长面条自己首尾相连而闭合”的事件用指示变量表示并求和。
- 形成单一大环的概率等于在每一步都“避免过早形成小环”的连乘概率（结果可写成一个连乘式）。
Original Explanation
Solution
First calculate expected number of loops: Denote X1 = identity variable, which takes value 1 every time a (long) noodle becomes a loop by connecting to its end, (if its own end is connected to some other noodle, then that other noodle's end will be considered). Thus, number of loops = X1 +...+ X100, thus, expected number of loops = E(X1) + ... + E(X100). This will give answer = 1/(2N-1) + 1/(2N-3) + ... + 1/3 + 1 where N = 100. This formula can also be proved using induction.
Calculating Probability of single large loop: If you followed last result, this one is simple, this time all the identitiy variables are zero except last one. Thus probability is [1 - 1/(2N-1)] * [ 1 - 1/(2N-3)] * ... * [1-1/3] = Product ( i = 2 to N) [ (2i-2) / (2i-1)]