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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
2  
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
4  
@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? – user59238 Jan 22 '13 at 15:54
up vote 50 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|cite|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
12  
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
    
Empirically it seems the probability of at least one triple birthday with $100$ people is closer to $0.64$ or $0.65% than $0.70$ – Henry Sep 6 '13 at 7:43
    
@Henry You are right, the exact probability is .6458645065. This Poisson approximation is not very good. – Byron Schmuland Jan 28 '14 at 23:09

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|cite|improve this answer
1  
Here is a good approximation based on two Poissons - one that overcounts and one that undercounts: $$P(W=0)=\frac 1 2\left(\exp\left(-T\right)+\exp\left(-\frac T{1+\frac{3(n-3)}{2m}} \right)\right)$$ where $T=(\frac 1 m)^2\binom n 3$ is expected number of triplets sharing a birthday and the second exponent is expected number of birth-days that are shared by at least $3$ people. The principle of averaging probabilities of $P(T)$ and $P(T/(1+\alpha))$ can be extended to other events, not just $W=0$. Yields $\approx 0.028537$ in this case. Change $3$ to $M$ for $M-plets$ of birthdays. – A.S. Dec 13 '15 at 16:54

Since this question has been linked to a question concerning the generalization to the case of $M$ people having the same birthday (Birthday paradox with M shared birthdays), I would like to add the general answer. Starting with the expression given by Michael Lugo (a derivation can be found here), it's rather easy to obtain the general solution. First, the expression can be simplified by using falling factorials:

\begin{equation} \displaystyle P(W\ge1) = 1 - \sum_{i=0}^{\lfloor n/2 \rfloor} \frac{(n)_{2i}(m)_{n-i}}{i! 2^i m^n} \end{equation}

where $(n)_k := n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$. The $i$th term in the sum represents the probability of having $i$ distinct pairs of people.

To generalize this result we note that the number 2 is just the size of a pair and can be replaced by any larger group size. However, we must be careful, since the $2^i$ in the denominator is really $(2!)^i$ (see the derivation for details).

Thus, if we want to know the probability that at least $M$ people from a group of $n$ share a common birthday, we sum over all group sizes smaller than $M$, replacing $2i$ in the numerator by $ki$ (where $k$ is the summation index) and $2^i$ in the denominator by $(k!)^i$:

\begin{equation} \displaystyle P(W\ge1) = 1 - \sum_{k=2}^{M-1}\sum_{i=0}^{\lfloor n/k \rfloor} \frac{(n)_{ki}(m)_{n-i}}{i! (k!)^i m^n} \end{equation}

share|cite|improve this answer

As being pointed out by Micheal Lugo the formulation given by Anirban DasGupta is a exact answer for this problem, however a formal proof is needed. I have found and verified a solution by Doctor Rick from Math Forum, below is the link

http://mathforum.org/library/drmath/view/56650.html

His approach is to partition the sample space as following:

   1.   none share a birthday
   2.   one pair shares a birthday
   3.   two pairs share different birthdays
   4.   three pairs share different birthdays
   :
 1+N/2. N/2 pairs share different birthdays
 2+N/2. three or more share a birthday

Then he points out a clever way to count for each partition by picking different birthday for each pair of person. I have tried and arrived with the same formulation as Anirban DasGupta's. For more detail please take a look at the link above!

share|cite|improve this answer
1  
You know this question is 4 years old right – dalastboss Mar 11 '15 at 5:25
    
I know, but just like me, someone will still look for the answer for it in future, and I think it hadn't got any good proof yet. I have verified that my proof is correct in my class! – minhta Mar 24 '15 at 16:42
    
Yep, in 2015 still looking at this answer.. – Pieter21 Nov 24 '15 at 18:55

My own research led to the following result...

Knowing that there are $A$ days in the year (typically $A=365$), the probability $P(A, M, n)$ that at least $n$ children have their birthday the same day within a class of $M$ children is:

$$\boxed{ P(A, M,n) = 1 - \dfrac{ K_n(A, M) }{ A^M } }$$

where $K_n(A, M)$ represents the number of configurations in which one cannot find $n$ children (or more) having their birthday the same day, and can be computed by recurrence as follows:

$$\forall n\ge 2, \quad \boxed{ K_{n+1}(A, M) = \sum_{0\le k\le \left\lfloor{\frac{M}{n}}\right\rfloor} \dfrac{ \binom{A}{k} \; (M)_{nk} \; K_n(A-k, M-nk)}{ (n!)^k} }$$

with the following initialization: $\boxed{ K_2(A,M)=(A)_M }$

and where $(n)_k$ stands for the decreasing factorial : $(n)_k = n(n-1)...(n-k+1)$

Numerically:

Within a class of $M=30$ children, knowing that the year counts $A=365$ days...

The probability that at least $n=2$ children have their birthday the same day is:

$$P(365,30,2)\simeq 70,6\%$$

The probability that at least $n=3$ children have their birthday the same day is:

$$P(365,30,3)\simeq 2,85\%$$

The probability that at least $n=4$ children have their birthday the same day is:

$$P(365,30,4)\simeq 0,0532\%$$

Nicolas

share|cite|improve this answer

Just like to point out that Trazom's answer is incorrect for the general case - the sets being counted in the outer sum overlap. I don't have enough reputation to comment. I wrote a blog post about the general case here : https://swarbrickjones.wordpress.com/2016/05/08/the-birthday-problem-ii-three-people-or-more/

share|cite|improve this answer

I am looking at this question and the complicated answers and it's confusing me. Supposing I want to solve in a group of 100 people. what is the probability that at least 3 people share a birthday. So I start from very basic - if there are 3 people, the probability of them sharing a birthday is $$\frac{1}{365} *\frac{1}{365}*\frac{1}{365}*(365)=\frac{1}{(365)^2}$$ 1/365 the prob. of 1 person having a birthday on a particular day multiplied by each person's probability multiplied by the total no. of days.
Similarly if there are 4 people, the probability of at least 3 of them sharing a birthday would be $\frac{1}{(365)^2}*^4C_3 $. and similarly for x people, $\frac{1}{(365)^2}*^XC_3 $

I am trying to find the fault in this logic.

share|cite|improve this answer
1  
Welcome to Math.SE! You have posted this as an Answer, but it really seems to be more of a new Question. If you wanted to understand why your computation is wrong, one approach would be trying to apply it to a simplified problem, such as "What is the probability that three people share the day of the week on which they were born?" But don't post as an Answer that the other answers are confusing to you. – hardmath Apr 8 at 18:50
    
No, what I meant is that I feel this is the answer, but I am not a 100% sure of it. It is just my attempt of answering the question but i would welcome critique on it. – yavvee Apr 8 at 18:56
1  
Let me briefly elaborate on how you can verify your approach is wrong. Note that a probability should always fall between $0$ and $1$, but as $X$ grows, your expression exceeds $1$. This is easily seen when we consider the days of the week simplification. The chance that three people are born on the same day of the week is indeed $\frac{1}{7^2}$, but the chance that three out of eight people share a day of week for birth cannot be $\frac{\binom{8}{3}}{7^2}$ because that exceeds $1$. – hardmath Apr 10 at 0:22

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.