k-Birthday Problem
May 21st, 2019 at 1:10:12 AM
permalink
Rambling preamble: This may be a duplicate thread. In this video, the Wizard says that there is a forum discussion about calculating the probability of at least 5 people out of n sharing a birthday, and that Mathematica calculates loops more efficiently than C++. I can't find the thread. However, I suspect that entirely different algorithms are being used in Mathematica and C++. I have a reasonably efficient solution in C++, and I was going to write up a post about it today, but as chance would have it, I saw and responded to this post instead. So instead, I'll throw it open, and post my solution this weekend (but the table below is reasonable evidence that I already have a solution).
Problem:
It is commonly known that a group of 23 people has a 50.7% chance that at least 2 people share a birthday. (Assuming, as one does in these problems, that birthdays are drawn independently and uniformly at random from the 365 days that are not Feb 29.)
Define the "k-birthday problem" as finding the least n such that, in a group of n people, the probability that at least k people share a birthday is at least 50% (with the same random birthday assumption).
How do you efficiently solve this problem, using a computer? (for cases where n ends up being in the thousands, but not much larger, let's say)
Efficiency is vague, but the following should be computable on a modern computer in much less than 30 seconds:
Bonus points for clear explanations and simple but efficient solutions. An arbitrary-precision arithmetic library might be helpful -- I used one to get large exact counts that I converted to the probabilities above -- but it is also possible to solve with floating-point arithmetic and minor rounding error.
Problem:
It is commonly known that a group of 23 people has a 50.7% chance that at least 2 people share a birthday. (Assuming, as one does in these problems, that birthdays are drawn independently and uniformly at random from the 365 days that are not Feb 29.)
Define the "k-birthday problem" as finding the least n such that, in a group of n people, the probability that at least k people share a birthday is at least 50% (with the same random birthday assumption).
How do you efficiently solve this problem, using a computer? (for cases where n ends up being in the thousands, but not much larger, let's say)
Efficiency is vague, but the following should be computable on a modern computer in much less than 30 seconds:
| k | n | probability that at least k out of n share birthday |
|---|---|---|
| 2 | 23 | 0.507297234323985 |
| 3 | 88 | 0.511065110624731 |
| 4 | 187 | 0.502685373188976 |
| 5 | 313 | 0.50107047584923 |
| 6 | 460 | 0.502449410369367 |
| 7 | 623 | 0.502948948664597 |
| 8 | 798 | 0.500320275210473 |
| 9 | 985 | 0.500948416381688 |
| 10 | 1181 | 0.500931161054311 |
Bonus points for clear explanations and simple but efficient solutions. An arbitrary-precision arithmetic library might be helpful -- I used one to get large exact counts that I converted to the probabilities above -- but it is also possible to solve with floating-point arithmetic and minor rounding error.
May 21st, 2019 at 9:08:43 AM
permalink
it hijacked another threadQuote: ZPPRambling preamble: This may be a duplicate thread. In this video, the Wizard says that there is a forum discussion about calculating the probability of at least 5 people out of n sharing a birthday, and that Mathematica calculates loops more efficiently than C++. I can't find the thread.
https://wizardofvegas.com/forum/gambling/tables/32745-roulette-16-number-board-history/3/#post709423
the original code was in Mathematica, I do remember that, (I think over at math.stackexchange.com) but that seems to have been removed as that author converted that into R (do not know or remember why) and only that remains.
I have not looked back at that.
good luck
thank you for sharing some of your great computer code and math results in the past.
winsome johnny (not Win some johnny)
