Thread: An extension of a birthday problem

1. An extension of a birthday problem

Hi

A few days ago, we were 3 in my class of 35 people to have the same birthday. That was quite a coincidence
But the wikipedia page about the birthday problem only deals with 2 people having the same birthday.

So I'd like to know how to compute the probability that out of n people, 3 (or more) have the same birthday ?

Thanks

2. Originally Posted by Moo
Hi

A few days ago, we were 3 in my class of 35 people to have the same birthday. That was quite a coincidence
But the wikipedia page about the birthday problem only deals with 2 people having the same birthday.

So I'd like to know how to compute the probability that out of n people, 3 (or more) have the same birthday ?

Thanks
Hello Moo,

Ross, "A First Course in Probability,7th edition", says the probability that no 3 of n people have the same birthday is "a difficult combinatorial problem", but he gives the following "good approximation".

Suppose we have a trial for each of the $\displaystyle \binom{n}{3}$ triplets i, j, k where $\displaystyle 1 \leq i < j < k \leq n$ and say we have a success if i, j, and k all have the same birthday. Then the number of successes is approximately a Poisson random variable with

$\displaystyle \lambda = \binom{n}{3} P(\text{i, j, k, have same birthday}) = \binom{n}{3} (1 / 365)^2 = \frac{n(n-1)(n-2)}{6 \times 365^2}$

Hence
$\displaystyle P(\text{no 3 have the same birthday}) \approx \exp \left( \frac{-n(n-1)(n-2)}{6 \times 365^2} \right)$

If you are looking for an exact solution, Julian Havil in "Nonplussed" refers to a 2004 paper by R.J. McGregor and G.P. Shannon, "On the generalized birthday problem", Mathematical Gazette 88(512):242-48, but Havil doesn't give any details and I don't have a copy of the paper handy.

Havil does say, quoting McGregor and Shannon, that the probability that at least 3 of 88 people will have the same birthday is about 1/2.

3. Originally Posted by Moo
So I'd like to know how to compute the probability that out of n people, 3 (or more) have the same birthday ?
Hi,

If you want an exact formula, this comes from simple combinatorics, but there's no "nice-looking" answer...: I get, for at least 3 simultaneous birthdays (let $\displaystyle N=365$)

$\displaystyle p=1-\frac{1}{N^n}\sum_{0\leq 2k \leq n}\frac{n!N!}{2^k k!(n-2k)!(N-(n-k))!}$.

I did not check the number 88 with Maple, it would be safer to try...

How I got the formula: we have to compute the number of $\displaystyle n$-uplets from $\displaystyle \{1,\ldots,N\}$ where the same value is not taken three times. The index $\displaystyle k$ in the formula stands for the number of pairs of matching birthdays (k=0 gives the usual case). For a given number $\displaystyle k$, and given the positions of the pairs, we have $\displaystyle N(N-1)\cdots(N-(n-k)+1)$ possibilities (we choose $\displaystyle k$ values for the pairs and $\displaystyle n-(2k)$ values for the others, all different). And for a given k, the number of positions of these k pairs is: $\displaystyle {n\choose 2k}(2k-1)(2k-3)\cdots 3\cdot 1$ (choice of the subset made by the pairs, and choice of the matchings). This gives a total number:

$\displaystyle \sum_{0\leq 2k\leq n}{n\choose 2k}(2k-1)(2k-3)\cdots5\cdot 3\cdot N(N-1)\cdots(N-(n-k)+1)$.

The previous formula follows after a mild rewriting.

I let you guess how ugly a general formula might look like...

PS. I forgot to mention: "Happy Birthday, Moo!"

4. Oops, I forgot to see look this thread afterwards...
Well, seems really ugly yeah... but it's not difficult to understand (though difficult to find... - gotta hate combinatorics)

Thank you awkward for your reference, I hope I'll find it in my university library (which I doubt, but nothing ventured, nothing gained)
Thank you Laurent for your formula. I guess there's no need to ask for a formula for an arbitrary m Would it have been easier to look for a formula for exactly 3 birthdays ? Yeah I know we can make probability of having > 3 - probability of having > 2, but is there a closer form ?
Note : I really suck at combinatorics, it's not that I'm too lazy to do it...

P.S. : thanks