Derivation of birthday paradox probability

Question

I am trying to come up with an explanation of the probability of birthday collision.

$P$(no collision among t people) = $(1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365})$

For one person, the probability of no collision is 1, which is trivial since a single birthday cannot collide with anyone else’s. For the second person, the probability of no collision is 364 over 365, since there is only one day, the birthday of the first person, to collide with:

$P$(no collision among 2 people) = $(1− \frac{1}{365})$

If a third person joins the party, he or she can collide with both of the people already there, hence:

$P$(no collision among 2 people) = $(1− \frac{1}{365})·(1−\frac{2}{365})$

While it is clear how we get the probability of collision for 2 people, it is not intuitive to me that how we get the probability of collision between 3 people. I'd expect the probability would be $(1−\frac{2}{365})$. For example, when you roll the dice, the probability of $6$ is $\frac{1}{6}$, and the probability for 5 or 6 is $\frac{2}{6}$. It is not $\frac{1}{6}$·$\frac{2}{6}$ which seems to be the case in birthday collisions.

I'd appreciate an answer with an intuitive explanation.

Answer 1

The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room.

Before the first person enters, there's no collision/coincidence of birth-date, thus probability of no collision is $P_0=1$.

When the first person enters, there can't be a collision/coincidence of birthdate, probability of no collision is $P_1=1$.

When the second person enters, there is one chance in $365$ that his/her birthday is the same as the first person's birthdate, thus the probability of no collision is $P_2=1-\frac1{365}$.

When the third person enters, either
- there was a collision at the previous stage, and then the probability of no collision is $0$;
- or there was no collision at the previous stage, thus there was $2$ persons with different birth-dates in the room, and the probability that the third person has one of their birth-dates is $2$ in $365$, thus the probability of no collision is $1-\frac2{365}$.
The total probability of no collision after the third person enters is obtained by adding these two probabilities weighted by the probability conditioning them. We thus have $P_3=(1-P_2)\,0+P_2\,\bigl(1-\frac2{365}\bigr)$, thus $P_3=\bigl(1-\frac1{365}\bigr)\bigl(1-\frac2{365}\bigr)$

The same reasoning gives $P_{i+1}=(1-P_i)\,0+P_i\bigl(1-\frac i{365}\bigr)$, that is $P_{i+1}=P_i\bigl(1-\frac i{365}\bigr)$.

From which it comes $P_t=\displaystyle\prod_{i=0}^{t-1}\,\Bigl(1-\frac i{365}\Bigr)$.

For derivation of formulas used in a cryptographic context where the numbers are huge, see my Birthday problem for cryptographic hashing, 101.
Note: $P$, $t$, and $365$ here are $q$, $n$ and $k$ there.

Answer 2

It may help to write it out using the chain rule of probability theory as:

\begin{align*} \Pr[\text{no collision among 2}] &= 1 - \frac{1}{365} \\ \Pr[\text{no collision among 3}] &= \Pr[\text{no collision with 3rd, and no collision among first 2}] \\ &= \Pr[\text{no collision with 3rd} \mid \text{no collision among 2}] \\ &\qquad \cdot \Pr[\text{no collision among 2}] \\ &= \biggl(1 - \frac{2}{365}\biggr) \biggl(1 - \frac{1}{365}\biggr), \end{align*}

and so on with $\Pr[\text{no collision among 4}]$, $\Pr[\text{no collision among 5}]$, etc.

In particular, $1 - \frac{n - 1}{365}$ is the probability that the $n^{\mathit{th}}$ person has a different birthday from the $n - 1$ prior persons, given that the $n - 1$ prior persons all have distinct birthdays—that is, $1 - \frac{n-1}{365}$ is $\Pr[\text{no collision with $n^{\mathit{th}}$}$ $\mid$ $\text{no collisions among $n - 1$}]$, but you read it as $\Pr[\text{no collision among $n$}]$.

Answer 3

Sometime back I did a detailed study of this problem.
So the problem was
"How many people(n) you need in a room such that m of them sharing birthday is 50%.?"
We know that for m=2, we need n=23 people such that probability of any two of them sharing birthday is 50%.

Suppose we have find n, such that probability of m=3 people share birthday is 50%.
We will calculate how 3 people out of n doesn’t share a birthday and subtract this probability from 1.

• All n people have different birthday.
• 1 pair (2 people) share birthday and the rest n-2 have distinct birthday.
  • Number of ways 1 pair (2 people) can be chosen = C(n, 2)
  • This pair can take any of 365 days
  • For these n-2 people they can pick 365–1 birthdays.
• Next we make 2 group of 2 people and rest n-4 have distinct birthday.
  Like this we can recursively create more groups and find all possible combination where m people doesn't share birthday.

https://medium.com/@c0D3M/birthday-paradox-3fd2f0f6c5a0