小球也能难倒人

wdcsss

有颜色各不相同的球，每次随机地从中取出两个球，然后给第1个取出的球涂上与第2个取出的球的颜色相同的颜色当所有的球都被涂上相同的颜色时，问:所需的操作数的期望是多少？

winxos

我想到点思路： 我们现将问题简化，假设只有2中颜色的球，比如说红和蓝，红色有`a`个，蓝色有`b`个，总数`a+b=n`个。 那么把颜色都刷成蓝色的概率应该是：第一次取红球，然后取蓝球，这样概率为`a/n b/(n-1)`，由于总数不变，我们要刷成蓝的话，下次应该还是第一次取红，然后取蓝，这样概率为`{(a-1)/n}*{(b+1)/(n-1)}`,以此类推，将所有概率连乘得到n个球都刷到蓝色的概率为`{a! (b+a-1)! }/{n^a (n-1)^a (b-1)!}` 然后应该可以扩展求得其他的概率。 以上只是一种想法，可能有错;)

mathe

这个问题要给出一般情况的公式很难.但是在问题不是太复杂的情况让计算机计算还是可行的. 这里我们需要考虑整个变换过程中可能出现的所有状态数. 比如如果有S个球,总共红蓝两种颜色,那么总共就有可能有S+1种状态,其中红色球数目分别为0到S种. 而如果有k种颜色,那么状态数相当于不定方程$x_1+x_2+...+x_k=S$的非负整数解的数目. 当然,其中有些状态对应的转移概率的关系是对称的,考虑到对称性,还可以消减很多状态. 比如总共4个球,红蓝两色,那么我们可以得到一个状态转移矩阵 $m=[(1,1/4,0,0,0),(0,1/2,1/3,0,0),(0,1/4,1/3,1/4,0),(0,0,1/3,1/4,0),(0,0,0,1/4,1)]$ 而任意一个初始状态都可以对应一个单位向量x.比如初始状态是两红两绿,那么就对应向量 $[(0),(0),(1),(0),(0)]$ 那么经过k步以后,各个状态的概率组成的向量就是$m^k*x$ 而只有到达第一个或者最后一个状态才是结束状态.所以最多k步结束的概率为 $y'*m^k*x$,其中$y'=[1,0,0,0,1]$ 而正好k步结束的概率就是$y'*m^k*x-y'*m^{k-1}*x$ 而计算这些值,我们可以通过对矩阵m求特征值来做到.比如上面的矩阵m,其特征多项式为 $-x^5+(37*x^4)/12-(27*x^3)/8+(71*x^2)/48-x/6-1/48-((x-1)^2*(48*x^3-52*x^2+10*x+1))/48$ 所以其特征值为两个1以及 -0.07158899680604716323052254389, 0.3714312331987845154986928071, 0.7834910969405959810651630702 分别记后面三个特征值为$r_1,r_2,r_3$ 那么不超过k步结束的概率必然可以写成$P(k)=ak+b+c*r_1^k+d*r_2^k+e*r_3^k$ 然后计算$P(1)=0,P(2)=1/6,P(3)=41/144,P(4)=653/1728,P(5)=9347/20736$ 我们可以解出a,b,c,d,e

mathe

比如上面的题,数值计算结果为a=0,b=0.71428571428574,c=0.18335728438775,d=-0.0051835853001094,e=-0.89245941337342

mathe

而上面计算结果还表明了另外一个有意思的结果,那么就是有1-0.71428571428574的概率无论操作多少次球也不会变成同色.所以对应的步数的期望值只能算是无穷大了

shshsh_0510

mathe说的不对，不会是无穷。这个马氏过程中只有全同色了是吸收态，把N步看成1步，其他状态向吸收态都是正概率，一定存在一个最小值，则期望值小于此值倒数

mathe

呵呵,我也觉得挺奇怪.不过现在仔细看了一下前面,发现问题了,m我写错了其中第4列中间的1/4要改成1/2

wdcsss

各位高人，我需要的是准确值

mathe

不一定有准确表示. 比如如果模型参数稍微大一点,得出的矩阵的特征方程通常次数就应该高于5次了,这时,至少特征值已经没有根式表示了,所以准确值已经不可能了