0
$\begingroup$

Disclaimer: I've seen posts with good answers for the case of "at least $2$ people", or "exactly $2$ people". Posts with "at least $k$ people" usually suppose that the mutual birthday is a fixed day (i.e. Jan 2nd) and apply the binomial distribution. This post has to do with the probability of $2$ people sharing the same (random) birthday in a group of $n$ people.


Attempt:

The probability of at least $2$ people having the same birthday in a group of $n$ people is the complement of the probability of everyone having a different birthday. That is: $$ p(n,k\geq 2)=1-\frac{365 \cdot 364 \cdot \dots \cdot (365-n+1)}{365^n} $$ Now, let's suppose that we want to find $p(n \geq 3)$. By making the assumption that $2$ people have already the same birthday, we can treat these two as one person. So the probability of at least $2$ people sharing the same birthday in a group of $n-1$ people is: $$ p(n-1,\geq 2)=1-\frac{365 \cdot 364 \cdot \dots \cdot (365-n+2)}{365^{n-1}} $$ Then, I'm thinking of finding the probability $p(n,k=2)$ of exactly $2$ people sharing the same birthday in a group of $n$ people and somehow calculate: $$ p(n,k\geq 3)=p(n-1,k \geq 2 \bigg| n,k=2) $$ but I'm possibly mistaken. Any thoughts?

$\endgroup$
  • $\begingroup$ The reason people tend to not write it up is that it gets very messy for general $k,n$. Even for $3,n$, it's messy because you need to consider the possibility that no two share a birthday, exactly two share a birthday, exactly two pair of people share birthdays (though not the same birthday) and so on. Not a difficult computation on a machine, but hard to do with pencil and paper. $\endgroup$ – lulu Feb 11 at 16:58
1
$\begingroup$

As far as I can tell, your methods do not work and cannot be salvaged.

This is a hard problem that cannot be solved by conventional means. To find the probability that at least three people have a common birthday, let us instead compute the probability that no three people share a birthday. This is equal to $$ \frac{n![x^n](1+x+x^2/2)^{365}}{365^n}.\tag 1 $$ Here, $[x^n]f(x)$ is the coefficient of $x^n$ in the polynomial $f(x)$. You want one minus the above. Another way to write this is $$ \sum_{a_1,a_2,\dots,a_{365}}\frac1{365^n}\frac{n!}{a_1!a_2!\cdots a_{365}!}.\tag 2 $$ where the sum ranges over all vectors $(a_1,a_2,\dots,a_{365})$ of integers between $0$ and $2$ whose sum is $n$. This works because each vector specifies a valid distribution of birthdays where no birthday repeats three times or more, and the multinomial coefficient gives the number of ordered selections of birthdays which have that distribution, and each is then multiplied by the probability $(1/365)^n$ of that ordered selection occurring. You can check that when you expand out $(1)$ and collect the coefficient of $x^{n}$, you get exactly $(2)$.


If you are okay with an approximate result, the expected number of triplets of people who share a common birthday is $\lambda =\binom{n}{3}\cdot \frac1{365}^2$, and the number of triplets with a common birthday is approximately Poisson with parameter $\lambda$. Therefore, the probability some triplet share a birthday is approximately $$ 1-e^{-\binom{n}3/365^2}. $$

$\endgroup$
  • $\begingroup$ Could you elaborate on how did you derive the first result, aka the probability that no three people share a birthday? $\endgroup$ – LoneBone Feb 11 at 22:42
  • $\begingroup$ @LoneBone See edit. $\endgroup$ – Mike Earnest Feb 11 at 23:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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