随机洗牌中的预期对数

机器算法验证 期望值
2022-04-08 05:06:19

假设有 34 个人随机站成一排,其中男性 18 人,女性 16 人。如果相邻的两个人属于不同的性别,我们认为他们是一对,我们平均期望看到多少对?

2个回答

首先,我们找到两个相邻个体具有不同性别的概率。这两个人同样可能是(342)对中的任何一个,其中18×16是男女对,所以这个概率是(18×16)/(342) .

对的总数是X1+X2++X33其中Xi是指示随机变量,如果人和 i+1 是异性,则为 1 ii+10。它的期望是E(X1)++E(X33),但是所有这些变量都具有相同的期望,即我们在上面找到的概率。所以答案是

33×18×16(342)=33×18×16(34×33)/2=18×1617=172117=1711716.94.

这与 Bernhard 的模拟一致。

更一般地说,如果你有个男性和个女性并且你遇到同样的问题mf

(m+f1)mf(m+f2)=(m+f1)mf(m+f)(m+f1)/2=2mfm+f

也可以通过仿真检查。

比我更聪明的人会发布一个理论和精确的解决方案。同时我的模拟尝试:

once <- function(){
    row <- sample(c(rep("m", 18), rep("f",16)))
    count <- 0
    for(i in 1:33){
        if(row[i]!=row[i+1]) 
        count <- count + 1
    }
    return(count)
}


run <- replicate(1e5, once())
plot(table(run))

在此处输入图像描述

> table(run)
run
    6     7     8     9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26    27    28    29 
    5    25    79   280   663  1643  3070  5555  8057 11169 12883 14309 12818 11020  7682  5279  2931  1535   635   261    78    17     4     2

> summary(run)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   6.00   15.00   17.00   16.96   19.00   29.00