I would like a better understanding of the famous birthday paradox. "What is the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday?"

I understood the first part, where the probability reaches 100% when the number of people reaches 367 by the pigeonhole principle. But I am not understanding the explanation beyond that. How do they say that the probability is 99.9% with 70 people and 50% with 23 people? And how do you further generalize the answer? And why is it a "paradox"?

• Please, post the explanation you have been given. Apr 2 '16 at 10:00
• en.wikipedia.org/wiki/Birthday_problem May be this is helpful to you Apr 2 '16 at 10:00
• @Mc Cheng it might be a bit more helpful to specify a section rather than referring someone to an article (which is debatable in its reliability) that is quite hard (and lengthy) to sort through Apr 2 '16 at 10:03
• I could've typed an answer but explanations of this paradox are readily available all over the internet. Take a look at the Wikipedia article. Tell me exactly what you cannot understand. Maybe then we'd be able to help. Apr 2 '16 at 10:03
• Apr 2 '16 at 10:11

Let the number of people in the group be $n$.

The probability that a pair of people don't share a birthday is given equal to $\frac{364}{365}$ ignoring leap years.

There are $\binom{n}{2}$ pair of people in a group of $n$ people. No pair of people will share a birthday if each person has a distinct birthday. The probability of this happening is given by

$$\frac{364}{365}\times\frac{363}{365} \dots \times \frac{365 - (n-1)}{365}$$

How did I get this probability?

Assume that all birthdays are equally likely. If the first person was born on day $x_1$ then the second person in the group cannot be born on day $x_1$. The probability for this happening is $364\over 365$. Now let the birthday of the second person be $x_2$. The probability that the third person is not born on $x_1$ nor on $x_2$ is $363\over365$. Similarly we get the probability for the $n^{\text{th}}$ person. Since each event is independent, we multiply all the probabilities.

Thus the probability that at least one pair shares a birthday for a group of $n$ people is given by

$$p = 1 - \left(\frac{364}{365}\times\frac{363}{365} \dots \times \frac{365 - (n-1)}{365}\right)$$

Now you have the probability $p$ as a function of $n$. If you know the RHS, then you simply find for what value of $n$ we get the closest RHS to $p$

It so happens that if $p = 99.9\%$, the $n = 70$

• Thank you Banach Tarski! Am I right in understanding, that the only reason it is a "paradox" is because we'd usually expect the probability to be linear in nature? I don't see any paradox otherwise Apr 2 '16 at 10:11
• @aswa09 yup you are correct. A paradox is a self contradictory statement. The contradiction here is with our common sense and not with the mathematics :) Apr 2 '16 at 10:15
• Is it not a multiplication of $364/365$ not $1/365$? Else your formula gives a $364/365$ chance of just two people sharing the same birthday Apr 2 '16 at 10:21
• Yes, I had made a blunder in computing the probability, I have fixed this now :) Apr 2 '16 at 10:39

The paradox is that the rate of growth doesn't match our common sense. We expect that the way to count the number of possibilities for people to have the same birthday is directly from the number of people. However, in reality it's based on the number of pairs of people, which grows much faster than the number of people.

Banach Tarski shows you the derivation which really is that the numerator is the number of people pairs, but still over 365.

• How do I remove the duplication mark? I have edited the question asking about why it's a paradox, so that it isn't a duplicate question Apr 3 '16 at 7:23