返回题库

变色球：全同色所需步数的期望

Color Balls

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

盒子里最初有 nn 个球，颜色两两不同。不断重复以下步骤：

  1. 随机选出一对球（有序），
  2. 把第一个球重新涂成第二个球的颜色，
  3. 把两球放回盒子。

问：直到 nn 个球都变成同一种颜色为止，所需步骤数的期望是多少？（很难）

A box initially contains nn balls, each of a different color. Repeatedly, you:

  1. Randomly select a pair of balls (order matters),
  2. Repaint the first ball to match the second ball’s color,
  3. Return both balls to the box.

What is the expected number of steps until all nn balls are the same color? (Very difficult)

解析

记 NnN_n 为达到全同色的步数。由对称性，最终颜色等概率落在任意一种初始颜色上。用吸收马尔可夫链（例如跟踪某“候选颜色”的球数）的分析可得到

E[Nn]=(n−1)2.\mathbb{E}[N_n]=(n-1)^2.

Original Explanation

Let NnN_n be the number of steps until all balls have the same color. By symmetry, each color is equally likely to be the final color, and the analysis (via absorbing Markov chain arguments on the number of balls of a “candidate” color) leads to the result: E[Nn]=(n−1)2.E[N_n] = (n-1)^2.