# What's wrong with this approach to the birthday problem?

I am trying to solve the following variation of the birthday problem. In summary, how many people is it necessary to gather together before the probability that two of them share the same birthday is greater than not? Assuming there are $365$ potential different birthdays, and the likelihood of each birthday is equal.

Given any two people, the probability that they share the same birthday is $1/365$. I then approached the question as how many distinct pairs of people would be needed before the total probability that any two of them shared a birthday is more than $1/2$, which I worked out as $\lceil365/2\rceil = 183$.

The smallest group of people for which there are more than $183$ distinct pairs is $20$, where there are $\frac{20\cdot19}{2} = 190$ distinct pairs. Therefore I concluded that the total probability of any two people sharing the same birthday was greater than evens for a group of $20$ people.

The true answer is that a minimum of $23$ people are required. I believe I am double counting somewhere or not taking into account mutual exclusivity, but can't quite see it. Any hints?

• The probability of at least one success in $N$ independent Bernoulli experiments with probability of success $p$ is not $N\cdot p$ but $1 - (1-p)^N$, since $(1-p)^N$ is the probability of no success. Thus you need $\left(\frac{364}{365}\right)^P < \frac{1}{2}$ rather than $\frac{P}{365} > \frac{1}{2}$. That gives $P \geqslant 253 = \frac{23\cdot 22}{2}$. – Daniel Fischer May 11 '14 at 18:12
• @DanielFischer So, the probability $P$ of at least one success after $n$ Bernoulli trials is $1-q^{n}$, where in this problem, $p = \frac{1}{365}$ and $q = 1 - p = \frac{364}{365}$. Then the number of Bernoulli trials $n$ necessary for the probability of at least one success to be more likely than not is the solution to the inequality $1 - (\frac{364}{365})^n > \frac{1}{2}$, which is equivalent to $(\frac{364}{365})^n < \frac{1}{2}$. And then the solution to $(\frac{364}{365})^n < \frac{1}{2}$ is $n \geq 253$ which translates to a group of 23 people. – James Hiew May 11 '14 at 19:02

Here you made the assumption that it would take $183/365$ pairs to get over $1/2$ probability. But there are more than $365$ possible pairs, and you did not account for if there's more than one matching pair. The easiest way to do this is to take the inverse, calculating the probability that no people have matching birthdays and then subtract $1$ from that probability. See Daniel Fischer's comment.
Suppose you have 3 people. That is 3 distinct pairs. What is the probability that 3 of them all have different birthdays? It isn't $\left({1 \over 2}\right)^3$.