2
$\begingroup$

I have followed the various birthday paradox posts. Can someone please assist with the logic for finding the probability of two pairs of people with the same birthday in a group of $23$. If $n=23$ gives us more than $0.5$ probability of one pair, what is the outcome for two pairs in the same population (assuming the second pair do not share the same birth date as the first pair)?

$\endgroup$
1
$\begingroup$

For the standard birthday problem, the number of possible sequences of $n$ birthdays that don't have two the same is $365\times364\times...\times(365-n+1)$ and so the probability that we don't have two the same after $n$ attempts is $\frac{365\times364\times...\times(365-n+1)}{365^n}=p_n$, which goes below $1/2$ at $n=23$.

The probability of either having all birthdays different or exactly one pair the same, all others different, or exactly three people the same, all others different is $$\frac{365\times...\times(365-n+1)+\binom n2365\times...\times(365-n+2)+\binom n3365\times...\times(365-n+3)}{365^n}\\=p_n\bigg(1+\binom n2\frac1{365-n+1}+\binom n3\frac1{(365-n+1)(365-n+2)}\bigg).$$ Thus we need to check when this is less than $1/2$. This first happens at $n=36$.

This assumes that you count any two pairs, including where both pairs have the same birthday. It would be more complicated to exclude this, and it shouldn't make very much difference, but as it happens the probability is actually very close to $1/2$ at $n=36$.

(edit: Actually, doing some more careful bounds, the probability of not having exactly one set of $2$, $3$ or $4$ the same, all others different at $n=36$ is $0.49944$. A simple bound on the probability of any configuration with $5$ or more people having the same birthday is the expected number of sets of $5$ people with the same birthday, and this is only $0.0000212$, not enough to tip the probability over $1/2$. So it is $n=36$ with either interpretation.)

| cite | improve this answer | |
$\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.