3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Daniel Fischer May 11 '14 at 18:12
  • $\begingroup$ @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. $\endgroup$ – James Hiew May 11 '14 at 19:02
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Suppose a year only has 2 days in it.

The probability that 2 people have a different birthday is 1/2.

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$.

$\endgroup$
  • $\begingroup$ Yes, when you have more people than days, the heuristic totally breaks down. But as long as there are many more days than people, it works reasonably well. $\endgroup$ – Daniel Fischer May 11 '14 at 18:23
  • 1
    $\begingroup$ Thanks, you are right of course, but since the poster didn't ask for a heuristic, and he seemed to suggest that the number of days was variable, and he did ask "what is wrong with this approach", I wanted to point out that "at some point this approach won't work"-- it tends to create a larger error further away from 50% as well, iirc. Yay for run on sentences. $\endgroup$ – DanielV May 11 '14 at 19:28
0
$\begingroup$

I think the part of the scenario that you are not accounting for is that in the case where there is already one shared birthday there are not n-1 days for n to match with, but n-2 (or n-3 if two shared birthdays etc.).

$\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.