The Pigeonhole

The formula for such pigeonhole questions is

q(n;d)= 1- (d-1/d)^n

where n is the total no of people, d is the total no of days on which birthday can coincide.

So q(1000;365)=1-(364/365)^1000 which is approximately 93.56%

Let $E$ be the event that my birthday matches with at least one other person. Then $not\ E$ is the probability that my birthday doesn't match with anyone.

We can write: $Prob(E) = 1 - Prob(not\ E) = 1 - \frac{N_{diff}}{N_{tot}}$ , where

$N_{diff}$ : number of possibilities of other peoples birthdays such that they don't match mine

$N$ : total number of possibilities of other peoples birthdays

• N1 = number of possibilities of my birthday = 1 (since my birthday is known/given)
• N 2 = number of possibilities of first person's birthday such that doesn't match mine = (365 -1) = 364
• N 3 = number of possibilities of second person's birthday such that doesn't match mine = (365 -1) = 364
• ...
• N 1000 = number of possibilities of 999th person's birthday such that doesn't match mine = (365 -1) = 364

Total number of possibilities of peoples birthdays such that it doesn't match mine = N1 x N2 x N3 x ... N1000 = 1 x $364^{999}$

Similarly total number of possibilities of peoples birthdays(without the matching constraint) = 1 x $365^{999}$

So $Prob(E) = 1 - Prob(not\ E) = 1 - \frac{364^{999}}{365^{999}} = 1 - (\frac{364}{365})^{999} = 0.935477 = 93.5477 \%$

The question is: in a group of $n$ people gathered for a birthday party, what is the probability that at least one person in the group has the same birthday as you? Let us denote the event that at least one person has the same birthday as you by $E$ . Then we have:

$P(E)$ = $1 -$ ( $\frac{364}{365}$ ) $^n$

In this case, $n$ = 1000. So we have that in a group of 1000 people gathered for a birthday party, the probability that at least one person has the same birthday as you is:

$P(E)$ = $1 -$ ( $\frac{364}{365}$ ) $^{1000}$ $\approx$ 93.56%