Birthday paradox

Question

We know that the probability of a person not having the same birthday as you is $\frac{364}{365}$ which is independent from person to person. Meaning the probability of having r people not having the same birthday as me is $(\frac{364}{365})^r$. now the probability that at least one person has the same birthday as me is 1-$(\frac{364}{365})^r$.

What is the smallest r that makes the probability greater than or equal to $\frac{1}{2}$

What i did was substituted random values for r in the calculator and found r to be $252$. I am looking for a reason why it is this number.

Answer 1

You want $$1-\left(\frac{364}{365}\right)^r \geq \frac{1}{2}.$$ Rearrange this inequality to obtain $$\frac{1}{2}\geq \left(\frac{364}{365}\right)^r.$$ Take $\log$ of both sides: $$-\log(2) \geq r\log\left(\frac{364}{365}\right),$$ so $$r \geq -\frac{\log(2)}{\log\left(\frac{364}{365}\right)},$$ which by wolfram alpha equals 252.7.

Answer 2

The number of people actually is $253$, not $252$. One way to see this is because calculation with logarithms (as shown in another answer) says $r \geq 252.65$. Another way is to use an accurate calculator to show that \begin{align} 1-(364/365)^{252} &\approx 0.4991, \\ 1-(364/365)^{253} &\approx 0.5005. \end{align}

That's the reason why it is that particular number; you're unlikely to find any explanation that is much more intuitive (other than something that will help you understand logarithms better, if that method seems difficult).

There is, however, an obvious reason why the number should be greater than $183$. That is because if you walk into a room with $N$ people already in it, the chance that one of them will share your birthday is precisely the chance that your birthday is on a particular list of dates composed of all the birthdays of the people in the room. And that chance is the same as the chance that any new person we might randomly find has a birthday on that list; in other words, we might as well consider your birthday to be random.

Since there are $365$ days that could possibly be on the list, the chance that a randomly selected day is already on the list is just $m/365$, where $m$ is the number of birthdays on the list. So in order to have $1/2$ chance or better that someone already in the room has your birthday, the people in the room must have $m$ different birthdays, where $m/365 \geq 1/2$; so $m \geq \frac12 \cdot 365 = 182.5$; and since $m$ must be an integer, $m \geq 183$.

The reason the number of people required is so much greater than $183$ is because you're so extremely unlikely to randomly select a group of $183$ people with all different birthdays. When you randomly gather that many people, you're almost certainly going to find some shared birthdays in the group; in fact you'll probably find quite a few shared birthdays, some shared by more than two people. The difference $253 - 183 = 70$ reflects the number of extra people you have to put in the room in order to counteract the "shared birthday" effect.