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.
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Isn't it simply $1-\frac{\binom{365}{95}}{365^{95}}$? $\endgroup$– barak manosCommented Feb 25, 2016 at 5:32
-
$\begingroup$ @barakmanos Your answer is for atleast $2$ . The question might be exactly $2$ $\endgroup$– Win VineethCommented Feb 25, 2016 at 5:37
-
$\begingroup$ @WinVineeth: Exactly two can be handled in a similar way. There are $\binom{95}{2}$ ways to choose the happy couple, and $365$ ways to choose their common birthday. Now count the number of ways to assign different birthdays to the remaining $93$ from the remaining $364$ days. $\endgroup$– André NicolasCommented Feb 25, 2016 at 5:54
-
$\begingroup$ @barakmanos I read $\binom{365}{95}$ as number of combinations; shouldn't it be a number of permutations? $\endgroup$– David KCommented Feb 25, 2016 at 18:53
-
$\begingroup$ For the "at least two" problem, there are several correct ways to reason about it, and several ways to express the resulting formula, which may look dramatically different but actually are exactly equal. That's the way it is with a lot of math problems. $\endgroup$– David KCommented Feb 25, 2016 at 18:55
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
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}}$
$\begingroup$
$\endgroup$
7
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}$.
-
$\begingroup$ You don't know whether it's exactly $2$ or atleast $2$ . Atleast $2$ is easy.. but not exactly $2$ $\endgroup$ Commented Feb 25, 2016 at 5:36
-
$\begingroup$ This cannot possibly be exact since if $n = 365$ the probability should be exactly $1$ but it won't be by this formula since $1 - \frac{\binom{365}{365}}{365^{365}} = 1 - \frac{1}{365^{365}} < 1$. $\endgroup$– JaredCommented Feb 25, 2016 at 5:39
-
1$\begingroup$ @Jared Why do you say the probability is $1$ if $n=365$? Even without leap year, there are $365$ days in a year, that's enough days for all $365$ of those people to have different birthdays. $\endgroup$– bofCommented Feb 25, 2016 at 5:47
-
$\begingroup$ @Jared that is not correct. For $n=365$ everybody could have a different birthday, but for $n>365$ this is not possible, and the formula gives exactly 1 in that case. $\endgroup$ Commented Feb 25, 2016 at 5:51
-
$\begingroup$ Actually, it can be wrong. As I haven't considered the permutation of birthdays. I'm gonna edit it out. $\endgroup$ Commented Feb 25, 2016 at 5:53