染成同色期望问题
一个坛子里有n(n>=3)个不同颜色的小球;每次从坛子里依次取出两个小球，将第二个小球染成第一个小球的颜色，再把这两个小球放回坛子里。问平均需要几次可以将坛子里n个球染成同一种颜色？ 对于通用情况，计算估计比较困难，但是对于较小的n,用计算机计算还是可行的。以4个球为例，我们可以把四球状态分为
4(4个球同色）
3+1(3个同色，1个不同色）
2+2（4个球两色，每色两球）
2+1+1
1+1+1+1
共5种不同状态
然后我们需要计算它们的状态转移矩阵
比如3+1状态，如果两个球都属于3，状态不变，概率1/2；第一个3，第二1，改为状态4，概率1/4；第一个1，第二个3，改为状态2+2,概率1/4.
最终我们可以得到如下状态转移图
然后我们可以得出方程组
E(4)=0
E(3+1)=1+1/4*E(4)+1/2*E(3+1)+1/4*E(2+2)
E(2+2)=1+1/3*E(2+2)+2/3*E(3+1)
E(2+1+1)=1+1/2*E(2+1+1)+1/3*E(3+1)+1/6*E(2+2)
E(1+1+1+1)=1+E(2+1+1)
解得
E(1+1+1+1)=9,E(2+1+1)=8,E(2+2)=7,E(3+1)=11/2
所以平均需要9步。
同样可以得到5个球时
对应需要16步。
计算计算更多球的情况，可以得到如下结果
(11:55) gp > (matid(4)-m)^-1*~
%11 = ~
(11:55) gp > ?ve
vecextract vecmin vecsearch vecsum vectorsmallversion
vecmax vecprod vecsort vector vectorv
(11:55) gp > m=;
(11:58) gp > (matid(4)-m/12)^(-1)*~
%13 = ~
(11:58) gp > m=;
(11:58) gp > (matid(6)-m/20)^(-1)*~
%15 = ~
<,0,24,6,0,0,0;0,0,0,0,0,0,0,20,5,0;0,0,0,0,0,0,0,8,14,8;0,0,0,0,0,0,0,0,18,12];
(11:59) gp > (matid(10)-m/30)^(-1)*~
%17 = ~
<0,0,0,0,0,30,6,0;0,0,0,0,0,0,0,0,0,0,0,10,22,10;0,0,0,0,0,0,0,0,0,0,0,0,12,30];
(12:00) gp > (matid(14)-m/42)^(-1)*~
%19 = ~
<,0,0,0,0,0,0,0,0,0,0,0,0,15,26,15;0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,32,24];
(12:00) gp > (matid(21)-m/56)^(-1)*~
%21 = ~
<,0,0,0,0,18,36,18;0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,52];
(12:01) gp > (matid(29)-m/72)^(-1)*~
%23 = ~
<0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,50,40];
<1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]~
%25 = ~
看来n个球平均需要$(n-1)^2$步 也有可能永远都染不成同一个颜色 mathe 发表于 2024-8-31 07:54
对于通用情况，计算估计比较困难，但是对于较小的n,用计算机计算还是可行的。
以4个球为例，我们可以把四球 ...
感谢，我大致明白您的思路，其实最后一个终点不能返回，没有“自回路“，可以看成是0,而不是1。 mathe 发表于 2024-8-31 07:54
对于通用情况，计算估计比较困难，但是对于较小的n,用计算机计算还是可行的。
以4个球为例，我们可以把四球 ...
我觉得这问题应该难在怎么确定递推关系式，本来处理一般情况的整数分拆是比较困难的。
页:
[1]