4
$\begingroup$

I found the following problem in an number of places online:

John once bet a fellow gambler that two of the first thirty persons they met and spoke to would prove to have the same birthday. Strong in the thought that he had 365 days running for him, the second hustler was pleased to accept. Suspecting, not unnaturally, a frame-up, he was careful to approach total strangers and chance passers-by, who could not be known to John. He lost the bet on the twenty-eighth question, when a duplicate birthday turned up.

“To tell you the truth,” said John afterward, “on each of the last five guys we spoke to, the odds were already better than even money in my favor. I'll explain the mathematics to you some time.”

Why is this true? At what point did John's chance of filling his bet pass 25%? 50%? 75%? 90%? 99%? (For your calculations, assume there are only 365 unique birthdays.)

N.B. John's statement about "the last five guys" assumes they will talk to all thirty people, regardless of whether the bet condition has been met or not, and the "better than even money" refers to the chance he will win the bet on or before that person.

$\endgroup$
  • 1
    $\begingroup$ "on each of the last five guys we spoke to, the odds were better than even money in my favor." I don't think this is true. You would need 183 birthdays before this was true. The problem as a whole is sound though. $\endgroup$ – Kendall Frey May 30 '14 at 19:08
  • $\begingroup$ @KendallFrey - not true. That was my initial reaction, but I can confirm that the probability passes 50% long before the 183rd person. $\endgroup$ – Xynariz May 30 '14 at 19:12
  • $\begingroup$ Not if you use the word 'each'. The probability of reaching one before 25 may be 50%, but the probability of getting a duplicate after 29 unique birthdays is 29/365. $\endgroup$ – Kendall Frey May 30 '14 at 19:15
  • $\begingroup$ Close, but not quite. Have you seen kaine's answer? The chance that the bet will be fulfilled by the 29th person is much larger than $\frac{29}{365}$. $\endgroup$ – Xynariz May 30 '14 at 19:17
  • $\begingroup$ That's not at all what I said. I was referring to the chances of the bet being fulfilled on a specific person (which is what the question erroneously says). $\endgroup$ – Kendall Frey May 30 '14 at 19:20
7
$\begingroup$

Probability two people have the same birthday: $\frac{1}{365}$

Probability that (if the first two of people don't have the same birthday) the third person is a duplicate: $\frac{2}{365}$

So the probability that by the third person, there is a duplicate is: $\frac{1}{365}+(1-\frac{1}{365})(\frac{2}{365})$

The probability that by the nth person they will have found a duplicate:

$P(n) = P(n-1)+(1-P(n-1))*\frac{n-1}{365}=\frac{n-1}{365}+P(n-1)\frac{366-n}{365}$

I don't feel like calculating this exactly by hand so:

$P(15) \approx .255$
$P(23) \approx .509$
$P(32) \approx .754$
$P(41) \approx .903$
$P(47) \approx .955$
$P(57) \approx .99$
$P(366) = 1$

These answers give the probability that he would win the bet by this turn. If, however, he were to say "Given that I have not yet won on turn $n-1$ the probability I will win on turn $n$ is greater than 50%" this does not occur so early. In this case, $P(n-1)=0$ so:

$P(n)=\frac{n-1}{365}$

In order for $P(n)>.5$ then

$n>183$.

$\endgroup$
  • $\begingroup$ This is the correct answer, with a nice formula to boot. $\endgroup$ – Xynariz May 30 '14 at 19:13
  • $\begingroup$ Thank you Kendall Frey for the OP's unintended second interpretation. $\endgroup$ – kaine May 30 '14 at 19:27
  • $\begingroup$ The question has been edited so that it is no longer ambiguous. $\endgroup$ – Xynariz May 30 '14 at 19:54
  • 1
    $\begingroup$ Further analysis can be had at wikipedia, where this problem has interesting implications for cryptographic hashing. $\endgroup$ – phs May 30 '14 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.