• There are 32,768 possible dates in a year (instead of 365) and people have a completely uniform random distribution of birthdays.
  • In each room there will be 3 people (if easy enough, alternate 3, 4, 3, 4).
  • New people are pulled into a new room 20 times a day.
  • This continues for 30 days.

Then what are the chances of a collision across the entire 30 days where two people in the same room have the same birthday?

Here's my best shot at solving it.

$$ 1 -\left(\frac{32767}{32768}^{3 \cdot 20 \cdot 30}\right) \approx 5.34509421\%$$

Or, as this may be a more useful way to think of it, after what number of days will there be a 50% chance of two people in the same room having had the same birthday?

Am I missing anything, here? What's throwing me off is that I know there's likely some kind of normal distribution that has to be accounted for, with standard deviations thrown in. The chances of 10,000 coin flips yielding 5,000 heads and 5,000 tails is not as high as one might think.

Also, how does it change things if instead of 20 distinct trials of four random people, instead random people with random birthdays enter and exit the room throughout the day, staying on average 10 minutes, with enough traffic that yields 20 instances of (max) four different people in the room at the same time? So if the room has A, B, C, D people, and A leaves, but then D enters, that's another "trial" of four different people. If person L is in the room and person M enters, that could be a collision right there. This kind of problem is much less familiar to me as to how I would try to solve it. I understand that the characteristics of the frequency, duration, and distribution of the visitors changes everything, so I don't know if it's even reasonable to ask this.

I'm trying to calculate the chances of collision, expressed in a meaningful sentence in English, if software build jobs that require a unique ID are given IDs at random from 1 - 32768. I don't know how long the jobs take. I guess they happen more during business hours across three times zones than outside (though there still are some).

  • $\begingroup$ You're not taking into account the pigeonhole principle. If there are 32, 769 people, then there is a 100% probability that two people will share the same birthday. Whatever formula you come up with has to equal 100% when n > 32,768...which your formula doesn't! $\endgroup$ – Konohamaru Mar 19 '19 at 2:02
  • $\begingroup$ I’m sorry, @TomislavOstojich, but it seems you have misunderstood the problem. There are only 4 people together in a room at once. That’s n = 4. There’s no n > 32768. $\endgroup$ – ErikE Mar 19 '19 at 3:39
  • $\begingroup$ you said there were 32768 possible birthdays (and aren't there only 365? What kind of calendar system are you using?) $\endgroup$ – Konohamaru Mar 19 '19 at 4:59
  • $\begingroup$ @TomislavOstojich There’s no calendar. There are no people. There are no rooms. All of that was analogy. Instead of 365 days in the “year,” there are 32,768. Perhaps it’s best if you find another question to answer? $\endgroup$ – ErikE Mar 19 '19 at 5:02
  • The probability a room with $3$ people has no collision is $\frac{32768}{32768}\times \frac{32767}{32768}\times \frac{32766}{32768} \approx 0.9999084$

  • The probability none of $20\times 30=600$ such independent rooms have a collision is that result to the power of $600$, which is about $0.9465485$

  • So the probability at least one of $600$ such independent rooms have a collision is $1$ minus that, about $0.05345147$

This is close to your result. It is not the same because you ignore the possibility of all three having the same birthday, but that event has an extremely low probability

Meanwhile, for your alternating $3,4,3,4,\ldots$ case, you can say

  • The probability a room with $4$ people has no collision is $\frac{32768}{32768}\times \frac{32767}{32768}\times \frac{32766}{32768}\times \frac{32765}{32768} \approx 0.9998169$

  • So the probability at least one of $300$ independent rooms with $3$ people and $300$ independent rooms with $4$ people have a collision is about $1-0.9999084^{300}\times 0.9998169^{300} \approx 0.07909658$

That is almost but not quite $1.5$ the previous figure, and that is not a coincidence. The probability of at least one collision with four in a room is almost double the probability of at least one collision with three in a room, related to $\frac{4 \times (4-1)}{3 \times (3-1)}=2$

Your people entering and leaving rooms case looks as if it would require more description of the precise mechanism; if you have compared a pair of people, you do not need to compare them again with each other when a third person enters the room

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.