变色次数的期望值的推广

056254628

niuhuang2003 的帖：变色次数的期望值
最后结果是$(2*n*m)/(n+m)$.
研究了三种颜色的变色次数问题，如红球R个，绿球G个，蓝球B个。
我计算了数值较小的部分，发现结果等于${2*(R*G+R*B+G*B)}/(R+G+B)$。
若再推广到n种颜色的球，每种球的个数分别是$K_1$，$K_2$，...，$K_n$。
那么变色的次数期望=$(2*\sum_{i,j,i!=j}K_i*K_j)/(\sum_{i=1}^{n}K_i)
这是我的猜想。

wayne

1# 056254628
猜想该是成立的,  这是我的 Mathematica代码：

1. 
   
2. x = {2, 3, 1,1};
   
3. bb = GatherBy [Map[Part[#, All, 1] &, Map[SplitBy, Permutations[Flatten[MapThread[Tuples[{#1}, #2] &, {Range[Length[x]],x}]]]]],Length[#] &];Sum[Length[ii]*(Length[ii[[1]]] - 1), {ii, bb}]/Total[Length /@ bb]
   

复制代码

输入x={2,3,1,1},表示 2个1，3个2，1个3，1个4 ,输出的结果34/7 即是 期望值。
如果想得到所有的排列情况，即变色次数为a的情况个数，代码是

1. Table[{Length[ii], (Length[ii[[1]]] - 1)}, {ii, bb}]

复制代码

输出结果{{24, 3}, {108, 4}, {192, 5}, {96, 6}} 表示  变色3次的情况有24种，变色4次的有108种，。。。

mathe

应该去猜测使用三种颜色各R,G,B次，然后分别是红绿蓝开头的序列的变色次数的期望值函数
r(R,G,B),g(R,G,B),b(R,G,B)

wayne

3# mathe
猜想:  对于三种颜色,各R,G,B次,分别的期望值是

${2(R*G+G*B+B*R)-G-B}/{R+G+B-1}$,  ${2(R*G+G*B+B*R)-B-R}/{R+G+B-1}$ ,   ${2(R*G+G*B+B*R)-R-G}/{R+G+B-1}$

对于n种情况： 每种球的个数是$K_m$
那么，对应的其变色的期望值是： ${2\sum_{i,j, i!=j} K_i*K_j-\sum_{i=1}^{n}K_i+K_m}/{\sum_{i=1}^{n}K_i-1}$

wayne

4# wayne
代码:

1. x = {2, 2, 1, 5};
   
2. bb = GatherBy [Map[SplitBy, Permutations[Flatten[MapThread[Tuples[{#1}, #2] &, {Range[Length[x]], x}]]]], #[[1, 1]] &];
   
3. Table[Sum[Length[ii]*(Length[ii[[1]]] - 1), {ii, GatherBy[k, Length[#] &]}]/ Length@k, {k, bb}]

复制代码

公式验证:

1. (2 Total[Map[Times @@ # &, Subsets[x, {2}]]] - Total[Map[Times @@ # &, Subsets[x, {1}]]] + x)/(Total[x] - 1)

复制代码

mathe

有了猜测，证明相对简单，用数学归纳法就可以，由于对于R,G,B都大于1我们有
$r(R,G,B)={R-1}/{R-1+G+B}r(R-1,G,B)+G/{R-1+G+B}(g(R-1,G,B)+1)+B/{R-1+G+B}(b(R-1,G,B)+1)$
检验一下，证明成立就可以了，同样我们需要检验$g(R,G,B)$和$b(R,G,B)$即可

056254628

公式这么简洁，一定有某种深刻的思想在里面。
经过这几天的思索，我有以下的思路，请大家鉴定。
-------------------------------------------------
n种颜色的球，第i种颜色的球的个数为$K_i.
所有球的个数s=$\sum_{i=1}^{n}K_i$
对于某种排列，计算它的变色次数，可以这么计算：
假设相邻位没有相同的颜色，那么变色次数=s-1
对于第i种颜色，如果它们1组相邻，那么变色次数就减1，
设某种排列第i种颜色相邻的组数为g(i),那么
该排列的变色次数=$(s-1)-\sum_{i=1}^{n}g(i)$
    例如1123223，变色次数=(7-1)-(1+1+0)=4
那么对于所有的排列(总排列数为N)，变色次数的期望值P=$(\sum^{N}((s-1)-\sum_{i=1}^{n}g(i)))/N$
=$s-1-\sum^{N}(\sum_{i=1}^{n}g(i)/N)$
=$s-1-\sum_{i=1}^{n}(\sum^{N}(g(i)))/N$

引入一种表示法u(i)=$\sum^{N}g(i)/N$，它表示排列中第i种颜色相邻的组数的期望值。
那么P=$s-1-\sum_{i=1}^{n}u(i)$
而u(i)=$(\sum_{j=1}^{K_i}C_{s-K_i+1}^{j}*C_{K_i-1}^{j-1}*(K_i-j))/(\sum_{j=1}^{K_i}C_{s-K_i+1}^{j}*C_{K_i-1}^{j-1})=(K_i-1)*K_i/s$    j表示某排列中第i种颜色被其他颜色分割成的区域数。
    例如  1001110011001    1被分割成4块区域。
所以P=$s-1-\sum_{i=1}^{n}((K_i-1)*K_i)/s$
     =$(s^2-\sum_{i=1}^{n}(K_i)^2)/s$
    将s^2展开二次项，化简得
    P=$(\sum_{i!=j}K_i*K_j)/s$      
因为$K_i*K_j=K_j*K_i$
所以也可以写出P=$(2*\sum_{i<j}K_i*K_j)/s $，就是我猜想中的公式。

056254628

受变色次数的期望值中suiyili的解法的启发，本题的结果几乎一气呵成：
假设相邻的球之间有一些连杆，连杆前后球的颜色不同，连杆值为1，相同连杆值为0，
题目所求的期望就等于连杆值和的期望。
设球的总数等于S，每根连杆的连杆值期望为E，
那么S=$\sum_{i=1}^{n}K_i$，连杆总数为S-1,
连杆值和的期望=$(S-1)*E$
假设E(i,j)表示连杆前端球的颜色为i，后端颜色为j的期望。
那么E=$\sum_{i!=j}E(i,j)$
而E(i,j)=$(K_i/S)*(K_j/(S-1))$=$(K_i*K_j)/(S*(S-1))$
因此题目所求的期望=连杆值和的期望=$(S-1)*E$
                                  =$(S-1)*\sum_{i!=j}E(i,j)$
                                  =$(S-1)*\sum_{i!=j}(K_i*K_j)/(S*(S-1))$
                                  =$(\sum_{i!=j}(K_i*K_j))/S$
                                 =$(\sum_{i<j}(2*K_i*K_j))/S$

niuhuang2003

太好了。结论竟然是如此的简单。