An extension of a birthday problem

**Moo** · December 19th 2009, 12:14 AM

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

**awkward** · December 19th 2009, 09:40 AM

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 $\binom{n}{3}$ triplets i, j, k where $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

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

**Laurent** · December 19th 2009, 02:11 PM

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 $N=365$ )

$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 $n$ -uplets from $\{1,\ldots,N\}$ where the same value is not taken three times. The index $k$ in the formula stands for the number of pairs of matching birthdays (k=0 gives the usual case). For a given number $k$ , and given the positions of the pairs, we have $N(N-1)\cdots(N-(n-k)+1)$ possibilities (we choose $k$ values for the pairs and $n-(2k)$ values for the others, all different). And for a given k, the number of positions of these k pairs is: ${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:

$\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!"

**Moo** · December 23rd 2009, 12:34 AM

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

Thread: An extension of a birthday problem

LinkBack

Thread Tools

Display

An extension of a birthday problem

Similar Math Help Forum Discussions

birthday problem

Birthday Problem

Yet another birthday problem

Advanced Birthday Problem

Birthday Paradox Problem!!

Search Tags