Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 23 down vote favorite
9

I have been looking at the birthday problem (http://en.wikipedia.org/wiki/Birthday_problem) and I am trying to figure out what the probability of 3 people sharing a birthday in a room of 30 people is. (Instead of 2).

I thought I understood the problem but I guess not since I have no idea how to do it with 3.

share|improve this question
Do we completely disregard the fact that people are more likely to be born on certain months than others? Making this slightly more likely? – fdart17 Mar 9 '11 at 4:27
2  
@Fdart17: In Exercise 13.7 of The Cauchy-Schwarz Master Class, J. Michael Steele uses Schur convexity to show that uniform probabilities are least likely to give birthday matches. So you are right, non-uniform birthdays give us a better chance of a match. – Byron Schmuland Mar 9 '11 at 16:32
Does the problem get simpler if you only want the probability that at least three people have the smae birthday? Does anyone have a solution for this problem? – Ed K Jan 22 at 15:54

2 Answers

up vote 30 down vote accepted

The birthday problem with 2 people is quite easy because finding the probability of the complementary event "all birthdays distinct" is straightforward. For 3 people, the complementary event includes "all birthdays distinct", "one pair and the rest distinct", "two pairs and the rest distinct", etc. To find the exact value is pretty complicated.

The Poisson approximation is pretty good, though. Imagine checking every triple and calling it a "success" if all three have the same birthdays. The total number of successes is approximately Poisson with mean value ${30 \choose 3}/365^2$. Here $30\choose 3$ is the number of triples, and $1/365^2$ is the chance that any particular triple is a success. The probability of getting at least one success is obtained from the Poisson distribution: $$ P(\mbox{ at least one triple birthday with 30 people})\approx 1-\exp(-{30 \choose 3}/365^2)=.0300. $$

You can modify this formula for other values, changing either 30 or 3. For instance, $$ P(\mbox{ at least one triple birthday with 100 people})\approx 1-\exp(-{100 \choose 3}/365^2)=.7029,$$ $$ P(\mbox{ at least one double birthday with 25 people })\approx 1-\exp(-{25 \choose 2}/365)=.5604.$$

Poisson approximation is very useful in probability, not only for birthday problems!

share|improve this answer
" and 1/365^2 is the chance that any particular triple is a success." - Hmm, I don't understand that part. Why squared? – GreenRails Mar 9 '11 at 16:22
4  
Take the three random people one at a time. The first guy has some birthday, say March 9. The chance that the second guy has the same birthday is 1/365, and the chance that the third guy has the same birthday is also 1/365. Multiplying these gives 1/365^2. – Byron Schmuland Mar 9 '11 at 16:25
Ah, that makes sense! Thanks for the great answer. – GreenRails Mar 9 '11 at 16:26
up vote 18 down vote

An exact formula can be found in Anirban DasGupta, The matching, birthday and the strong birthday problem: a contemporary review, Journal of Statistical Planning and Inference 130 (2005), 377-389. This paper claims that if $W$ is the number of triplets of people having the same birthday, $m$ is the number of days in the year, and $n$ is the number of people, then

$$ P(W \ge 1) = 1 - \sum_{i=0}^{\lfloor n/2 \rfloor} {m! n! \over i! (n-2i)! (m-n+i)! 2^i m^n} $$

No derivation or source is given; I think the idea is that the term corresponding to $i$ is the probability that there are $i$ birthdays shared by 2 people each and $n-2i$ birthdays with one person each.

In particular, if $m = 365, n = 30$ this formula gives $0.0285$, not far from Byron's approximation.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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