生日悖论:如何以编程方式估算3个和N个共享生日的人的概率 [英] Birthday Paradox: How to programmatically estimate the probability of 3, and N, people sharing a birthday

问题描述

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

There are extensive resources on the internet discussing the famous Birthday Paradox. It is clear to me how you calculate the probability of two people sharing a birthday i.e. P(same) = 1 - P(different). However if I ask myself something apparently more simple I stall: firstly, let's say I generate two random birthdays. Getting the same birthday is like tossing a coin. Either the two persons share a birthday (Heads) or they don't share a birthday (Tail). Run this 500 times and the end result (#Heads/500) will somehow be close to 0.5

• Q1)但是，如果我随机产生三个生日，我会怎么想呢?那我怎么估计概率呢?显然，我的硬币比喻将不适用.

• Q1) But how do I think about this if I generate three random birthdays? How can I estimate the probability then? Obviously my coin analogy won't be applicable.

Q2)一旦我确定了以上内容，我将需要扩大规模并产生30或50个生日.是否有推荐的技术或算法可以将相同的生日与较大的生日隔离?我应该将它们放入数组并遍历它们吗?

Q2) once I have figured out the above I will need to scale it up and generate 30 or 50 birthdays. Is there a recommended technique or algorithm to isolate identical birthdays from a large set? Should I put them into arrays and loop through them?

这是我认为我需要的:

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?

Q2)

• Create an array for 2 duplicates, an array for 3 duplicates and one for more than 3 duplicates
• add each generated birthday one by one into the first array. But before doing so, loop through the array to see if it's in there already. If so, add it to the second array, but before doing so repeat the above process and so on
• It doesn't seem to be a very efficient algorithm though :) suggestions to improve the Big O here?

推荐答案

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

Create an integer array of length 365, initialized to 0. Then generate N (in your case 25) random numbers between 1-365 and increase that number in the array (ie. bdays[random_value]++). Since you are only interested in a collision happening, right after increasing the number in the array check if it is greater than 2 (If it is then there is a second collision, which means there are 3 people with the same birthday). Keep track of collisions and execute this as many times as you wish (1000).

最后，碰撞比例/1000将是您要求的值.

In the end, the ratio of collisions/1000 will be your requested value.

而且，没有抛硬币的比喻是错误的.

and, no tossing coins analogy is wrong.

这篇关于生日悖论:如何以编程方式估算3个和N个共享生日的人的概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！