盒子里的彩色球
盒子里有\(n\)种颜色的球，第\(i\)种颜色的球初始时有\(a_i\)个。玩家每轮进行如下操作：
- 从盒子中依次取出两个球，记为\(\text f, \text s\)。
- 若\(\text f\)和\(\text s\)颜色不同，则将\(\text f\)的颜色重刷成\(\text s\)的颜色。
- 将两个球放回盒子。
求直到所有的球具有相同的颜色为止，经过轮数的数学期望。
解答
注意到所有的颜色是对称的，那么我们只需指定其中一种颜色分析，记这种颜色为\(c\)，其他颜色统称\(\bar c\)。记当这种颜色的球的数目为\(i\)时为状态\(i\)。
记\(s = \sum_{i=1}^n a_i\)为所有球数。
记\(f_i\)为从状态\(i\)到状态\(s\)，需经过轮数的数学期望，则\(f_s = 0\)。记\(q_i\)为从状态\(i\)能够转移到状态\(s\)的概率，由于题目不需要指定颜色，故最终结果为
\[ \sum_{i=1}^n q_{a_i} f_{a_i}. \]
在状态\(i\)下：
- 选出两个球颜色情况恰为：先取出一个\(c\)，后取出一个\(\bar c\)的概率为
\[ p_{i+1} = \frac{i(s-i)}{\binom s 2}, \]
此时，重刷后，两球颜色均为\(c\)，状态\(i\)将变成\(i+1\)。同理，\(p_{i-1} = p_{i+1}\)。
- 选出两个球颜色均为\(\bar c\)或均为\(c\)的概率为
\[ 1 - p_{i+1} - p_{i-1}, \]
故状态转移方程为
\[ f_i = p_{i-1} f_{i-1} + p_{i+1}f_{i+1} + (1 - p_{i-1} - p_{i+1})f_i + 1. \tag{?} \]
这个方程有点不对劲儿，这是因为没有考虑转移失败的情况。
考虑状态\(i=1\)到\(i=0\)，注意到，一旦进入状态\(0\)，所有的球就不再可能具有这种颜色，故不再可能转移到状态\(s\)。注意到\(p_{i+1} = p_{i-1}\)，这是一个两端吸收壁的对称随机游走模型，故状态\(i\)在到达\(0\)之前到达\(s\)的概率为
\[ q_i = \frac{i}{s}. \]
于是，基础概率从\(1\)变成\(q_i\)。正确的转移方程为
\[ q_if_i = q_{i-1} p_{i-1} (f_{i-1}+1) + q_{i+1} p_{i+1} (f_{i+1}+1) + q_i(1 - p_{i-1} - p_{i+1})(f_i + 1), \]
注意到\(2q_i = q_{i-1} + q_{i+1}\)，\(p_{i-1} = p_{i+1}\)，我们有
\[ q_i f_i = q_{i-1} p_{i-1} f_{i-1} + q_{i+1} p_{i+1}f_{i+1} + q_i(1 - p_{i-1} - p_{i+1})f_i + q_i. \]
代入化简得
\[ 2if_i = (i-1)f_{i-1} + (i+1)f_{i+1} + \frac{s(s-1)}{s-i}. \tag{*} \]
注意到上式的高度对称性。令
\[ g_i = if_i - (i-1)f_{i-1}, \tag{1} \]
可知\(g_1 = f_1\)。两边求和有
\[ \sum_{i=1}^n g_i = \sum_{i=1}^n i f_i - \sum_{i=1}^n (i-1)f_{i-1} = nf_n. \tag{2} \]
(*)式结合(1)式有
\[ g_{i+1} - g_i = -\frac{s(s-1)}{s-i}, \]
累加得
\[ g_n = g_1- \sum_{i=1}^{n-1} \frac{s(s-1)}{s-i}, \tag{3} \]
两边求和，联立(2)式得
\[ nf_n = \sum_{i=1}^n g_i = ng_1 - \sum_{i=1}^n \sum_{j=1}^{i-1} \frac{s(s-1)}{s-i} = ng_1 - \sum_{i=1}^{n-1} (n-i)\frac{s(s-1)}{s-i} \]
令\(n=s\)，得
\[ sf_s = 0 = sg_1 - \sum_{i=1}^{s-1}(s-i) \frac{s(s-1)}{s-i} = sg_1 - \sum_{i=1}^{s-1} s(s-1), \]
化简得
\[ g_1 = f_1 = (s-1)^2. \]
求得\(f_1\)后，即可用(*)式进行线性递推，得到最终结果\(\sum_{i=1}^n q_{a_i} f_{a_i}\)。时间复杂度\(O(s)\)。
特例
当\(\forall i, a_i = 1\)时，最终结果为\(\sum_{i=1}^n \frac{1}{n}(n-1)^2 = (n-1)^2\)。