小球也能难倒人

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次了,这时,至少特征值已经没有根式表示了,所以准确值已经不可能了