返回题库

染色球合并：期望步数

n balls in a bag

专题
Probability / 概率
难度
L4

题目详情

There are nn balls in a bag, colored from 1 to nn . In each step, a pair of balls is chosen uniformly at random from all the pairs of differently colored balls, and then the second ball of the chosen pair is painted with the color of the first ball. Finally, both balls are placed back into the bag. What is the expected number of steps it takes for all the balls to be of the same color?

解析

设 TT 为最终所有球同色所需步数。

对每种颜色 ii，记录“颜色 ii 的球数”在每次发生变化时的取值序列，可证明它等价于在 {0,1,…,n}\{0,1,\ldots,n\} 上、从 1 出发的对称随机游走，吸收于 0 或 nn。

令 XiX_i 为颜色 ii 被选入那对球的总次数，则有

T=12∑i=1nXi.T=\frac{1}{2}\sum_{i=1}^n X_i.

由对称随机游走从 1 到达 {0,n}\{0,n\} 的期望时间为 n−1n-1，故 E[Xi]=n−1\mathbb{E}[X_i]=n-1，于是

E[T]=12∑i=1n(n−1)=n(n−1)2.\boxed{\mathbb{E}[T]=\frac12\sum_{i=1}^n (n-1)=\frac{n(n-1)}{2}}.