The birthday paradox?

Question

So let's say there's a room with 95 people in it. If you asked all 95 people what their birthday is, what are the chances that you'll find two people with the same birthday. I've read through my textbook and looked through my notes but I can't seem to figure out how this works. I've got an equation that looks like $1 - (1-1/d)(1-2/d)...(1-(n-1)/d)$ which converges to $e^{-n^2/2d}$. Is that the formula that I use to find the probability because I keep seeing a ton of different equations and ways to do this and it's confusing me like crazy.

Answer 1

Let's try to find a simpler way that works. It might be arduous to calculate buy it's easier to understand. Let's say there are $n$ people in a room. Let's forget about leap years. So, there are only $365$ possible birthdays. So, the number of possible combination of birthdays is $365^n$ because everyone has $365$ choices and everyone's choices are independent.

Now, let's see how many possible combinations there are so that everyone has distinct birthdays. Let's assume $n \leq 365$ or it'd be obvious that at least two of them have the same birthday. Now, we can do that in ${365 \cdot 364 \cdot \cdot \cdot (365-n+1)=\frac{365!}{(365-n)!}=^{365}P_n}$ ways. So, the chance of that happening would be $\frac{ ^{365}P_n}{365^n}$ the probability we are seeking is the compliment of this case. So, the chance of finding two men with the same birthday would be $1- \frac{ ^{365}P_n}{365^n}$.

Answer 2

Finding the probability that at least two people have the same birthday is the same as taking 1 minus the probability that no one has the same birthday. So let's look at the probability no one has the same birthday.

Say we have 95 people in a room all without the same birthday. There are 365 possible birth dates that the first person can have, 364 for the second person, etc. Without any restrictions, there are $365^{95}$ ways 95 people can have any birth date.

So the probability that 95 people in a room do not have any birth date in common is: $\frac{365}{365}*\frac{364}{365}*...*\frac{271}{365}=(1-0/365)(1-1/365)*...*(1-(95-1)/365)$

Therefore the probability that at least two people in a room have a common birth date is: $1-(1-0/365)(1-1/365)*...*(1-(95-1)/365)$

replace 365 with d and 95 with n to get your result.

This value can be approximated by $e^{-n^2/2d}$ using the Taylor series expansion of $e^x=1+x+x^2/2!+...$

If we take the first order approximation, we have $e^x{\approx}1+x$

So, $1-n/x{\approx}e^{-n/x}$.

Therefore,

$(1−1/d)(1−2/d)...(1−(n−1)/d){\approx}e^{-\frac{1+2+3+...+(n-1)}{d}}=e^-{\frac{n(n-1)}{2d}}{\approx}e^{-\frac{n^2}{2d}}$