2
$\begingroup$

I am working on the problem of birthday paradox:

How many people do you need to reach 50% chance of at least one pair with matching birthday?

When I first heard the problem I verified the answer 23 by subtracting possibility of 23 people with different birthdays from 1.

$$ 1 - \frac{{}_{365} \mathrm{P}_{23}}{365^{23}} $$

I assumed this should work as people are distinguishable objects and 23 people have ${}_{365} \mathrm{P}_{23}$ permutations of not matching birthdays.

And yet according to scientific american article one should calculate

$$ 1 - \left(\frac{364}{365}\right)^{\sum_{ i = 1 }^{22} i}$$

because we make $\sum_{ i = 1 }^{22} i$ comparisons and two people have $\frac{364}{365}$ chance of not matching birthday.

Am I missing something here?

$\endgroup$
4
  • $\begingroup$ What problem are you working on? what do you mean by "verified the answer 23"? $\endgroup$
    – user99914
    Commented Jul 31, 2016 at 5:06
  • $\begingroup$ Oh sorry I thought birthday paradox was a proper noun not a generic class of problems. I was working on original(?) wording : How many people do you need to reach 50% chance of at least one pair with matching birthday. $\endgroup$
    – user357393
    Commented Jul 31, 2016 at 5:11
  • $\begingroup$ I could somehow guess the problem, but probably not able to guess that you are working on 50% chance. I'll edit your question. $\endgroup$
    – user99914
    Commented Jul 31, 2016 at 5:16
  • $\begingroup$ The article appears to be wrong... $\endgroup$
    – Clement C.
    Commented Jul 31, 2016 at 5:18

1 Answer 1

Reset to default
0
$\begingroup$

The first method is exact. The article's method is an approximation. What you are looking for is the Reverse Birthday Problem, which has a nice approximation.

$\endgroup$
2
  • $\begingroup$ Thanks! Wording of birthday paradox was more intricate than I expected it to be. My understanding of combinatorics is really elementary and I'm really uncomfortable with approximations. So when one assumes "two people sharing the same birthday" as independent events, does it mean to consider people as indistinguishable objects by ignoring past comparisons? $\endgroup$
    – user357393
    Commented Jul 31, 2016 at 5:44
  • $\begingroup$ The birthdays themselves are independent events. Two people sharing the same birthday is one singular event. The exact answer considers people only as birthdays, and the idea behind it looks more like someone filling up a calendar with birthdays than actual comparisons between two people. The part after the "$1-$" in the first formula is the probability that two people do not share the same birthday. $\endgroup$
    – AlgorithmsX
    Commented Jul 31, 2016 at 6:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .