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?
Best Answer
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.