有n个球排成一列，每个球都有一个颜色，用A-Z的大写字母来表示，我们每次随机选出两个球ball1,ball2,使得后者染上前者的颜色，求期望操作多少次，才能使得所有球的颜色都一样？
输出保留一位小数。
单独考虑每种颜色
设当前颜色个数为\(i\)，令\(g_i\)为到达目标状态的概率，有\(g_i=\frac{1}{2}(g_{i-1}+g_{i+1})\)，边界\(g_0=0,g_n=1\)
同理，令\(f_i\)为到达目标状态的期望步数，这里的期望指能到达目标状态的，所以对于每种转移，还得算起能到达目标状态的概率
然后有个结论是：\(g_i=\frac{i}{n}\)，可进一步化简成
原文：https://www.cnblogs.com/Grice/p/12548764.html