2

互联网上有大量资源讨论著名的生日悖论。我很清楚你如何计算两个人共享生日的概率，即P(same) = 1 - P(different)。但是，如果我问自己一些显然更简单的问题，我会拖延：首先，假设我生成了两个随机生日。获得相同的生日就像扔硬币一样。两个人要么共享一个生日（Heads），要么他们不共享一个生日（Tail）。运行 500 次，最终结果 (#Heads/500) 将接近 0.5

  • Q1) 但是，如果我生成三个随机生日，我该如何考虑呢？那我该如何估计概率呢？显然我的硬币类比不适用。

  • Q2）一旦我弄清楚了上述情况，我将需要扩大规模并生成 30 或 50 个生日。是否有推荐的技术或算法从大集合中分离出相同的生日？我应该将它们放入数组并循环遍历它们吗？

这是我认为我需要的：

Q1)

r = 25 i.e. each trial run generates 25 birthdays

Trial 1 >
3 duplicates: 0

Trial 2 >
3 duplicates: 0

Trial 3 >
3 duplicates: 2

Trial 4 >
3 duplicates: 1

...

T100 >
3 duplicates: 2

estimated probability of 3 persons sharing a birthday in a room of 25 = (0+0+2+1+...+2)/100

Q2)

  • 为 2 个重复项创建一个数组，为 3 个重复项创建一个数组，为超过 3 个重复项创建一个数组
  • 将每个生成的生日一个一个地添加到第一个数组中。但在这样做之前，请遍历数组以查看它是否已经存在。如果是这样，将其添加到第二个数组中，但在此之前重复上述过程，依此类推
  • 虽然它似乎不是一个非常有效的算法:) 建议在这里改进 Big O？
4

3 回答 3

2

创建一个长度为 365 的整数数组，初始化为 0。然后在 1-365 之间生成 N 个（在您的情况下为 25 个）随机数，并在数组中增加该数字（即 bdays[random_value]++）。由于您只对发生碰撞感兴趣，因此在增加数组中的数字后立即检查它是否大于 2（如果是则存在第二次碰撞，这意味着有 3 个人的生日相同）。跟踪碰撞并根据需要执行多次（1000）。

最后，碰撞/1000 的比率将是您要求的值。

而且，抛硬币的比喻没有错。

于 2011-02-15T11:21:46.227 回答
0

在 CrossValidated 上查看这个类似的问题及其答案，但我认为再次考虑经典的生日问题以获取基础知识确实值得。

对于您问题的第二部分：取决于您使用的语言。我绝对建议使用R来解决这样的问题，因为在列表/向量/数据框中检查相同的生日可以通过简单的unique调用轻松完成。要运行如此简单的 MC 模拟 R 再次非常方便，请查看上面链接中的第二个答案。

于 2011-02-14T13:12:45.280 回答
0

听起来您的第一个任务是创建一个生成随机生日的方法。为简单起见，您可以使用数字 1-365 来表示唯一的生日。

然而，在 ArrayList 中将许多随机生日（第一种情况下为 2 个）作为字符串存储。您将需要使用循环来调用随机数函数并将值存储在列表中。

然后创建一个函数来搜索 ArrayList 中的重复项。如果有任何重复（无论有多少），那么这就是正面结果。如果没有匹配项，则为 Tails。

在您达到 20 左右之前，您的概率将与 50/50 相差甚远。

于 2011-02-14T22:39:02.190 回答