变色次数的期望值的推广

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代码：

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

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

niuhuang2003

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