机器算法验证 - 生日“悖论”——换个角度 - 吾爱随笔录

生日“悖论”——换个角度

机器算法验证可能性假设检验采样生日悖论

2022-03-14 09:35:16

背景：很多人都熟悉所谓的生日“悖论”，即在一个 23 人的房间里，两个人同一天生日的概率超过 50/50。在对 n 个人更一般的形式中，没有两个人生日相同的概率是。类似的计算用于理解散列空间大小、密码攻击等。 $p(n) = \frac{365!}{ 365^n *(365-n)!}$

动机：提出以下问题的原因实际上与了解特定的金融市场行为有关。然而，“生日悖论”问题的一个变体完全适合类比，并且可能会引起不同背景的人更广泛的兴趣。因此，我的问题是按照更熟悉的“生日悖论”来构建的，如下所示。

情况：一个房间一共有60个人。其中，事实证明有 11 (11) PAIRS 人的生日相同，还有一个 TRIPLE（即 3 人一组）生日相同。剩下的 60 - 2*11 - 3 = 35 人的生日不同。假设一个人口中任何一天生日的可能性都相同（即忽略 2 月 29 日和可能的季节性影响），并且给定生日的指定分布，提问者想了解这 60 人的可能性（或不太可能）真的是随机选择的。这个问题最初是在另一个没有回答的网站上提出的，但建议提问者以下面的形式重新陈述这个问题。

问题：“如果从人口中随机选择 60 个人，其中任何一天都是一个人的生日，那么有 11 天恰好有 2 个人共享生日，有 1 天恰好有 3 个人生日的概率是多少？他们中的一个人同一个生日，没有 4 个或更多人同一个生日的日子？”

2个回答

如有疑问，请模拟。（我相信您实际上可以组合一个公式，但看起来可能会很痛苦。）我将使用“至少一个三重生日”和“至少十一个双生日”的标准——更改下面的代码以检查这么多生日并不难。

n.sims <- 1e5 n.persons <- 60

counter <- 0
pb <- winProgressBar(max=n.sims)
for ( ii in 1:n.sims ) {
    setWinProgressBar(pb,ii,paste(ii,"of",n.sims))
    set.seed(ii)
    birthdays <- sample(x=365,size=n.persons,replace=TRUE)
    birthday.table <- table(birthdays)
    if (    sum(birthday.table>=4) == 0  &
                sum(birthday.table==3) >= 1  &
                sum(birthday.table==2) >= 11 ) counter <- counter+1
}
close(pb)
counter/n.sims

在 100,000 次模拟中，我得到了 6 次命中，值为。如果你旋转命令，例如 to ，你会得到稍微不同的结果（在这种情况下），它作为一种敏感性分析。 $p$ $p=0.00006$ set.seed()set.seed(2*ii) $p=0.00004$

假设您的目标是恰好（至少不是）发生 11 个双生日和 1 个三重生日：

\begin{aligned} p (60, n_{2} = 11, n_{3} = 1) & = \frac{possibilities with 11 double birthdays and 1 triple birthdays}{all possibilities} \\ = \frac{\frac{60!}{35! 22! 3!} 21!! \cdot 365 \cdot 364 \cdot . . . \cdot (365 - n + 1 + 1 \cdot 11 + 2 \cdot 1)}{365^{60}} \end{aligned}

$\begin{align}p(60,n_2=11,n_3=1) &= \frac{\text{possibilities with 11 double birthdays and 1 triple birthdays}}{\text{all possibilities}}\\ &= \frac{\frac{60!}{35!22!3!} 21!! \,\cdot \,365 \cdot 364 \cdot \, ... \, \cdot (365-n+1+1\cdot11+2\cdot1)}{365^{60}}\end{align}$

我在 R 中的计算

factorial(60)/(factorial(35)*factorial(22)*factorial(3))*
pracma::factorial2(21)*
cumprod(319:365)[47]/365^60

近似为 $3.64 * 10^{-5}$

计算中的术语解释

$365^{60}$ 是在同样可能的 365 天中随机选择 60 个生日的方法数。
$365 \cdot 364 \cdot \, ... \, \cdot (365-n+1+1\cdot11+2\cdot1)$ 是在同样可能的 365 天中随机选择 60-11-2 天的方法数。
$\frac{60!}{35!22!3!}$ 是将 60 人分成 35、22 和 3 组的唯一方法数（单生日、双生日和三生日的人数）
$21!! = 21 \cdot 19 \cdot ... \cdot 3 \cdot 1$ 是我们可以将双生日组中的 22 人分成对的方式数。

其它你可能感兴趣的问题

上一篇随机森林中的低解释方差（R randomForest）下一篇通过 LDA 的所有成对分类进行多类分类