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)