3
$\begingroup$

A couple weeks back, I was seeing if I could solve the basic formulation of the Birthday Problem (i.e. assuming 365 equally likely birthdays, what's the probability that, given a room of ${n}$ people, at least one pair of people share a birthday). The initial solution that I used was to treat this as a binomial problem. There are $\binom {n} {2}$ ways to pick a pair out of a room of ${n}$ people, and the probability of those two people not sharing a birthday is $\frac{364}{365}$. Thus, the probability of having no pairs of people in the room with a shared birthday is $\left(\frac{364}{365}\right)^\binom{n}{2}$, assuming that the probability of two people sharing a birthday is independent of all other pairs sharing a birthday. Since we are interested in the probability of at least one pair of people, the final answer to the problem would be the complement of the above:

$$ 1 - \left(\frac{364}{365}\right)^\binom{n}{2}$$

In checking my work against the internet, I came across the accepted answer, which hinges on comparing each person in the room against anyone previously analyzed. So the second person has a $\frac{364}{365}$ chance of not colliding with the first birthday, the third person has a $\frac{363}{365}$ chance of not colliding with the first and second birthdays, and so on. Generalizing this comparison process to ${n}$ people, and then taking to complement probability, we get a final answer of:

$$ 1- \frac{\binom{365}{n} {n}!}{365^{n}}$$

My question: What is the initial solution above failing to take into account that makes it produce different results from the accepted answer? I can see that the equations we derive for any room size ${n}$ within both solutions are different, but conceptually where does the initial solution break down?

If I had to take a guess, I would say that the problem with my initial solution lies in "assuming that the probability of two people sharing a birthday is independent of all other pairs sharing a birthday," but I'm still struggling to grasp why that independence assumption is invalid...

Any help would be appreciated. Thanks!

P.S. In case my explanation of the two methods was unclear, both are detailed on the Birthday Problem Wikipedia page. What I termed the "accepted answer" is detailed in the section "Calculating the Probability", while my "initial solution" is under the section "A simple exponentiation."

$\endgroup$
8
$\begingroup$

Yes, the independence assumption is invalid.

Suppose you know that Alice and Bob have different birthdays, and you also know that Bob and Carol have different birthdays. What is the chance that Alice and Carol have different birthdays? Is it still 364/365? No. Suppose Bob was born at day X. Alice was NOT born at the day X. Since X is not the Carol's birthday, either, we now have 364 days in which Alice could've born, one of them is Carol's birthday. The probability is 363/364, rather than 364/365.

$\endgroup$

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.