Birthday problem variation

  • Thread starter tjaeger
  • Start date
  • #1
8
0

Main Question or Discussion Point

So, I've been trying to solve a variation of the famous birthday problem. The problem is a more generalized version and goes like this: given n people, what is the probability at least k people share a birthday? You could also describe the problem as such: given m items randomly distributed into n bins (a probability 1/m of an item being put into a bin) what is the probability that at least one bin has at least k items. I've been searching the internet for ways to try to solve this problem, but I haven't had much luck. Is there a name for this type of problem or does anyone have any insights on this problem?

My first intuition on how to solve this problem would be to use a computer program to calculate all the ways the items can be distributed for n items and finding out how many of the ways have bins have bins with k or more items.

For instance, if n = 5 the items can be distributed as follows:
1+1+1+1+1, 2+1+1+1, 3+1+1, 2+2+1, 3+2, 4+1, 5

Then, for each of these partitions find out how many ways they can be spread out over m bins. However, this becomes infeasible quickly because for n=100 there are 190569292 possible partitions and for n=1000 there are 24061467864032622473692149727991 partitions.
 

Answers and Replies

Related Threads on Birthday problem variation

  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
4K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
2K
Replies
1
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
6
Views
193
Replies
8
Views
3K
Top