3
$\begingroup$

There is that classic question about how many people in a room is required so that at least one pair of people share a birthday, with > 50% probability, the answer is 23. The standard textbook solution is to solve it using:

$$\mathbb{P}\left(\text{At least one shared birthday}\right) = 1 - \mathbb{P}\left(\text{zero shared birthdays}\right)$$

Since the probability of zero shared birthdays is easier to calculate/derive. From what I know, this is calculated as the series:

$$\mathbb{P}\left(\text{zero shared birthdays}\right)=\frac{365-1}{365}\times\frac{365-2}{365}\times\ldots\times\frac{365-22}{365}$$

the above makes sense, because for each successive person in the group, they can't share any birthday with any previous person, so the number of available days diminishes by 1 each time.

However, I am really struggling to derive $\mathbb{P}\left(\text{At least one shared birthday}\right)$, without using the inverse. Some sort of recursion/series is the way to go, something like:

$$\mathbb{P}\left(\text{23 people share at least 1 birthday}\right)=x+\mathbb{P}\left(\text{22 people share at least 1 birthday}\right)$$

I believe the base cases are: $$\mathbb{P}\left(\text{1 person share a birthday}\right)=0$$ $$\mathbb{P}\left(\text{2 person share a birthday}\right)=1/365$$

Can someone help me derive it, perhaps by spelling out the series?

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Indeed, just take $$p_1=0\quad \quad p_n=p_{n-1}+\frac {n-1}{365}\times (1-p_{n-1})$$

The logic being: in order to have at least one pair with $n$ people, you must either have a pair with the first $n-1$ of them, or you must have no pair with the first $n-1$ but the $n^{th}$ person must match one of the prior $n-1$ birthdays. And of course these two events are mutually exclusive.

$\endgroup$
8
  • $\begingroup$ pretty intense, I think it makes sense $\endgroup$
    – Alexander Mills
    Nov 1, 2020 at 23:50
  • $\begingroup$ correct answer, but I guess I don't quite understand how the OR here gets rid of the extra intersection of the 2 events? usually there's a subtraction component in the formula, aka P(A or B) = P(A) + P(B) - P(A and B) $\endgroup$
    – Alexander Mills
    Nov 2, 2020 at 0:02
  • 1
    $\begingroup$ @AlexanderMills There is no intersection, since my second event presupposes that the first does not occur. $\endgroup$
    – lulu
    Nov 2, 2020 at 0:03
  • 1
    $\begingroup$ Be sure you are clear on the meaning of my two events. My first event is "there is at least one match amongst the first $n-1$ people". My second event is "there is no match amongst the first $n-1$ people but the $n^{th}$ person matches one of the first $n-1$". Those events are clearly mutually exclusive. $\endgroup$
    – lulu
    Nov 2, 2020 at 0:05
  • 1
    $\begingroup$ @AlexanderMills No. Say $A=B$, and that neither $P(A)$ nor $P(A^c)=0$. $\endgroup$
    – lulu
    Nov 2, 2020 at 0:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .