12
$\begingroup$

What is the probability that in a randomly chosen group of $r$ people at least three people have the same birthday?

  1. $\displaystyle 1- \frac{365\cdot364 \cdots(365-r+1)}{365^r}$
  2. $\displaystyle \frac{365\cdot364 \cdots(365-r+1)}{365^r} +{r\choose 2}\cdot \frac{365\cdot364\cdot363 \cdots (364-(r-2) +1)}{364^{r-2}}$
  3. $\displaystyle 1- \frac{365\cdot364 \cdots(365-r+1)}{365^r} +{r\choose 2}\cdot \frac{365\cdot364\cdot363 \cdots (364-(r-2) +1)}{364^{r-2}}$
  4. $\displaystyle\frac{365\cdot364 \cdots(365-r+1)}{365^r} $

My attempt :

(May be typo in option $(3)$ of question !)

$$P(\text{at least 3 persons have same birthday})$$

$$= 1 - \{P\text{(no one has same birthday) + P(any 2 have same birthday)\}}$$

So, option $(3)$ is true.

Can you explain it, please?

It asked here before, but I'm not satisfied by explanation.

$\endgroup$
  • 1
    $\begingroup$ The problem is quite complicated. First of all, we have to remove the case of pairwise different birthdays. But then, we have to remove the case of $1$ pair , $2$ pairs , ... $[r/2]$ pairs with the same birthday (but every pair has another birthday). $\endgroup$ – Peter Nov 24 '15 at 15:36
  • 2
    $\begingroup$ There is no correct answer among 1-4. However, 3 answers a different question. Namely, call a pair $\{i,j\}$ a collision if persons $i$ and $j$ have the same birthday. Then the probability that there are at least two collisions is given by 3. $\endgroup$ – zhoraster Dec 13 '15 at 13:49
  • $\begingroup$ Consider the following scenario: persons A and B have birthday X while persons C and D have birthday Y. This sort of situation is not accounted for if you're only counting ways there can be precisely one pair of persons sharing a birthday. It is possible for multiple pairs of persons to share birthdays without any three sharing a birthday. $\endgroup$ – anon Dec 20 '15 at 7:06
  • 1
    $\begingroup$ Note that the first two terms of 3. match with the first two terms of my answer. That is, $1-P(\text{no one has the same birthday})=1-\frac{365!}{(365-n)!}$. However, $P(\text{any $2$ have the same birthday})$ is unclear. First, it sounds as if it might include a case where $3$ people have the same birthday. Secondly, in 3., the third term is added when it should be subtracted (after changing it to be the probability of at least one pair, but no triples). $\endgroup$ – robjohn Dec 20 '15 at 14:49
11
+50
$\begingroup$

Given $2k$ items, there are $(2k-1)!!$ ways to arrange them into pairs: the first item can be paired with $2k-1$ possibilities; the first unpaired item can be matched with $2k-3$ items; the new first unpaired item can be paired with $2k-5$ items; etc.

The number of functions from $n$ people to $365$ dates with $n-2k$ singles and $k$ pairs is $$ \begin{array}{cc} &\displaystyle\underbrace{ \overbrace{\binom{365}{n-k}}^{\substack{\text{ways to choose}\\\text{$n-k$ dates}\\\text{for birthdays}}} \overbrace{\binom{n-k}{k}}^{\substack{\text{ways to choose}\\\text{$k$ dates}\\\text{for pairs}}} }&\displaystyle\underbrace{ \overbrace{\ \ \binom{n}{2k}\ \ }^{\substack{\text{ways to choose}\\\text{$2k$ people}\\\text{for pairs}}} \overbrace{(n-2k)!\vphantom{\binom{n}{k}}}^{\substack{\text{ways to arrange}\\\text{$n-2k$ singles}}} \overbrace{(2k-1)!!\vphantom{\binom{n}{k}}}^{\substack{\text{ways to pair}\\\text{$2k$ people}}} \overbrace{\ \ \ \ \ k!\ \ \ \ \ \vphantom{\binom{n}{k}}}^{\substack{\text{ways to arrange}\\\text{$k$ pairs}}} }\\ \displaystyle= &\displaystyle\frac{365!}{(365-n+k)!\,(n-2k)!\,k!} &\displaystyle\frac{n!}{2^k} \end{array} $$ Thus, the probability of getting at least one triple is $$ 1-\frac{365!\,n!}{365^n}\sum_{k=0}^{365}\frac1{(365-n+k)!\,(n-2k)!\,k!\,2^k} $$ where we take $\frac1{n!}=0$ for $n\lt0$.

Here is a plot from $n=0$ to $n=730$. For $n\lt3$, the probability of getting a triple is $0$, and for $n\gt730$, the probability is $1$.

enter image description here

$\endgroup$
  • $\begingroup$ Is there double factorial? $\endgroup$ – 1 0 Dec 16 '15 at 11:06
  • $\begingroup$ Double Factorial $\endgroup$ – robjohn Dec 16 '15 at 12:54
5
$\begingroup$

Before we start with calculations we should think about which values of $r$ we should take into account.

  • $r=1,2$: We can exclude the trivial cases $r=1$ and $r=2$ which give a probability of zero, since we never reach a configuration with three people having the same birthday.

  • $2<r\leq 365$: The main part where we put the focus of our analysis. Fortunately the reasoning can be easily extended to $r\leq 730$.

  • $365<r\leq 2\cdot 365$: Assuming the year has $365$ days, the situation becomes slightly different if the number of people is greater than $365$. In these cases it is guaranteed that there are people with the same birthday and this needs some additional thoughts.

  • $r>2\cdot 365$: According to the pigeonhole principle groups with more than $730$ people have at least three equal birthdays with probability $p=1$.


Starter:

In order to get a first impression and to have a verification for small numbers at hand we look at a smaller example. It should be small enough to make calculations easy and large enough to be representative for the problem.

We take $r=5$ people and instead of $365$ days we use $6$ days. If we take a fair die with six faces instead, this smaller version of the problem can then be stated as:

Small Problem: What is the probability that in a group of $5$ people, each of them throwing a fair die once, at least three people roll the same number.

Five people can throw a total of $6^5=7776$ different configuration of $5$-tuples from $(1,1,1,1,1)$ to $(6,6,6,6,6)$.

We answer the question by counting the $5$-tuples which have no more than two equal faces.

  • Let $N_{(11111)}$ be the number of $5$-tuples with pairwise different entries. We see that there are $6\cdot5\cdot\ldots\cdot1=6!$ possibilities and get \begin{align*} N_{(11111)}=6!=720 \end{align*} The index $11111$ indicates that there are five pairwise different values counted.

Now we consider the number of $5$-tuples with one or more pairs of equal numbers, but with no occurrence of three or more equal numbers. There are two different constellations:

  • One pair and three other numbers which are pairwise different, denoted by $N_{(1112)}$.

  • The second constellation are two different pairs and another number different to each of them, denoted by $N_{(122)}$.

    We obtain \begin{align*} N_{(1112)}&=\frac{1}{1!}\binom{5}{2}6\cdot5\cdot4\cdot3=3600\tag{1}\\ N_{(122)}&=\frac{1}{2!}\binom{5}{2}6\binom{3}{2}5\cdot4=1800\tag{2} \end{align*}

Comment:

  • In (1) there are $\binom{5}{2}$ pairs which can take the values $1,\ldots,6$. The other three people have $5,4$ and $3$ possibilities to throw a number pairwise different to all the others.

  • In (2) there are $\binom{5}{2}\cdot6$ possibilities for one pair, leaving $\binom{5-2}{2}\cdot5$ possibilities for the second pair. Since we don't want to count different pair constellations more than once, we have to divide them by $2!$.

The distribution table of all different $5$-tuples can be easily calculated

\begin{array}{cccccccc} \text{Total}&N_{(11111)}&N_{(1112)}&N_{(113)}&N_{(122)}&N_{(14)}&N_{(23)}&N_{(5)}\\ 7776&\color{blue}{720}&\color{blue}{3600}& 1200& \color{blue}{1800} & 150 & 300 & 6 \end{array}

We are ready to calculate the wanted probability $p$ for this small example:

\begin{align*} p&=1-\frac{N_{(11111)}}{6^5}-\left(\frac{N_{(1112)}}{6^5}+\frac{N_{(122)}}{6^5}\right)\\ &=1-\frac{720}{6^5}-\frac{5400}{6^5}\\ &=1-\frac{6120}{7776}\\ &=0.212963 \end{align*}


The real problem:

Most of the work has been done by the small example. If we now consider $365$ days and $r$ people we can go on straight forward.

At first we put the focus at

\begin{align*} 3\leq r \leq 365 \end{align*}

  • Let's denote with $N_{(1^{r})}$ the number of $r$-tuples with all entries pairwise different. The exponent in the index $1^{r}$ denotes the multiplicity of $1$.

We obtain \begin{align*} N_{(1^{r})}=\frac{365!}{(365-r)!}\tag{3} \end{align*}

Next we have to consider $r$-tuples containing $k$ pairs of tuples, with $1\leq k\leq \lfloor\frac{r}{2}\rfloor$ together with $r-2k$ single numbers pairwise different to all other single numbers and numbers within tuples. We denote them with $N_{(1^{r-2k}2^k)}$.

We obtain analogously to (2) \begin{align*} N_{(1^{r-2k}2^k)}&=\frac{1}{k!}\binom{r}{2}365\binom{r-2}{2}364\cdots\binom{r-2(k-1)}{2}\left(365-(k-1)\right)\\ &\qquad\cdot(365-k)\cdots((365-k)-(r-2k-1))\\ &=\frac{1}{k!}\binom{r}{2}\binom{r-2}{2}\cdots\binom{r-2(k-1)}{2}\frac{365!}{(365-(r-k))!}\\ &=\frac{1}{k!}\frac{r!}{2^k(r-2k)!}\frac{365!}{(365-(r-k))!}\tag{4} \end{align*}

Plausibility check: If we compare the expression (4) with the small example above we could do a simple check. If we set \begin{align*} r=5,k=2,\text{ and }365\rightarrow 6 \end{align*} we obtain \begin{align*} N_{(1^{5-4}2^2)}=N_{(12^2)}=\frac{1}{2!}\frac{5!}{2^2(5-4)!}\frac{6!}{(6-(5-2))!} =1800 \end{align*} in accordance with the table entry $N_{(122)}$ above.

The range $365<r\leq 2\cdot 365$

If $r>365$ it is guaranteed that at least two people have the same birthday. It follows $$N_{(1^r)}=0$$ We see after short consideration, the approach (4) for a group of people with $1\leq k\leq \lfloor r\rfloor$ distinct pairs is also valid up to $r\leq 730$.


Now it's time to harvest. In order to find the number of all $r$-tuples we have to exclude, we sum up $N_{(1^r)}$ and $N_{(1^{r-2k}2^k)}$ for $1\leq k \leq \lfloor\frac{r}{2}\rfloor$.

In fact, inspired by the comment of @robjohn, we can also respect all other values of $r$ in the same formula, if we take $\frac{1}{n!}=0$ for $n<0$ and finally obtain

The probability $p$ that at least three people from a group of $r\geq 1$ people have the same birthday is according to (3) and (4)

\begin{align*} p&=1-\frac{1}{365^r}\left(N_{(1^r)}+\sum_{k=1}^{\lfloor\frac{r}{2}\rfloor}N_{(1^{r-2k}2^k)}\right)\\ &=1-\frac{365!}{365^r}\left(\frac{1}{(365-r)!} +r!\sum_{k=1}^{\lfloor\frac{r}{2}\rfloor}\frac{1}{2^kk!(r-2k)!(365-(r-k))!}\right)\\ &=1-r!\frac{365!}{365^r}\sum_{k=0}^{\lfloor\frac{r}{2}\rfloor}\frac{1}{2^kk!(r-2k)!(365-(r-k))!} \end{align*}

$\endgroup$
  • $\begingroup$ I worked on my answer offline, so I didn't see your answer before I posted. Since we got the same result, I assume your answer is correct. However, I have not had a chance to go through your answer yet. Do you need that the domain be $3\le r\le365$? My answer should work for all $n\ge0$. At $n=730$, it gives $1-\frac{730!}{2^{365}365^{730}}$ and for $n\gt730$, it gives $1$. $\endgroup$ – robjohn Dec 14 '15 at 4:27
  • $\begingroup$ @robjohn: Good to see, that our results coincide for $r\leq 365$. Due to the pigeonhole principle the probabiliy is equal to $1$ for $r>730$, I agree. The range $365 < r \leq 730$ is not that obvious for me, since with probability $1$ we have at least two birthdays equal. I will think about it after work and I will also have a more closer look to your arguments. Thanks for your comment. Regards, $\endgroup$ – Markus Scheuer Dec 14 '15 at 7:28
  • $\begingroup$ @MarkusScheuer, Why is wrong option $(3)$? $\endgroup$ – 1 0 Dec 14 '15 at 9:03
  • $\begingroup$ @MithleshUpadhay: It does not properly respect the possibilities of more than one equal pair. Maybe it is helpful, if you have a more closer look at the part around tag (2) of my answer, together with the comment for (2). $\endgroup$ – Markus Scheuer Dec 14 '15 at 9:16
  • 1
    $\begingroup$ @MarkusScheuer: Indeed. The terms in the sum all vanish for $n\gt730$. Less obvious is that the sum evaluates to $1$ for $0\le n\le 2$. Of course it should since no triple can be formed with fewer than $3$ people. $\endgroup$ – robjohn Dec 14 '15 at 19:36
3
$\begingroup$

There are three possible situations: either 1. everyone has a different birthday, 2. there are 1 or more pairs of birthdays, but no triplets, 3. there is any triplet. The three situations add up to all possible situations.

The calculations for each of the cases:

  1. You have the possibility to have all different birthdays: $365 \choose r$
  2. You have the possibility that there is any pair that has the same birthday, this can be calculated with inclusion/exclusion method, taking into account that there can be $1,2,3,..,(r/2)$ pairs. Please invest the time to fully understand the inclusion/exclusion method. Counting the combinations with $(a,b)$ having the same birthday regardless of $c, d$, has to exclude counting twice $(c,d)$ having the same birthday (though different from $(a,b)$.
  3. Final solution: ${(365^r - 1. - 2.)} / {365^r}$

More elaborate discussion on: Probability of 3 people in a room of 30 having the same birthday

Where you obviously have to generalize to $r$ iso 30. (And take the second answer, the first is only an estimation)

Note: Maybe it is more clear when you have 6 people throwing dice. What is the probability that no 3 throw the same number?

There can be 0..3 pairs of pairs. Extend this solution to 365 sided dice, and $r$ people.

$\endgroup$
  • $\begingroup$ Can you explain ? $\endgroup$ – 1 0 Dec 13 '15 at 8:01
  • $\begingroup$ Can you tell which part of the answer is not clear? (While I'll expand on the answer a bit.) $\endgroup$ – Pieter21 Dec 13 '15 at 11:04
  • 1
    $\begingroup$ How you are using inclusion-exclusion here? Part 2 and 3 need to expand. $\endgroup$ – 1 0 Dec 13 '15 at 11:11
  • $\begingroup$ Expanded part 2. Part 3. did not need to expand, because it is just the rest of the universe. $\endgroup$ – Pieter21 Dec 13 '15 at 11:20
  • 1
    $\begingroup$ @Pieter21: It would be nice, if you could elaborate your hint about the inclusion-exclusion principle in some detail. Your approach could provide some additional insight. $\endgroup$ – Markus Scheuer Dec 13 '15 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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