Was Arthur C. Clarke Right About the Birthday Paradox?

[mugaliens]

http://en.wikipedia.org/wiki/Arthur_C._Clarke" was a great author. What many don't know is that he was a very good inventor, as well as a statistics afficionado, his acclaim here, I suspect, as an auditor in the pensions section of the Board of Education (London Gazette: no. 34321, p. 5798, 8 September 1936. Retrieved on 2008-03-19.), although his interests along these lines may have been helped considerably with his Kings College degree in Mathematics he earned after the war.

Given: Everyone on a bus has an equal chance of having a birthday on any given day of the year.

Find: How many people must be aboard the bus for the odds of any single person having a birthday on today's date to be greater than 50%.

Ahh... Sounds easy! I know the answer, and in 1994, I actually worked out the proof, despite the fact that I was (and am still not) either a math or a statistics teacher.

So, my challenge to you is:

Post the Proof supporting your answer.

Hint: The answer is 23 (until I'm proven wrong).

And as a very interesting side note, he worked on various predictions between 1958 to 1962, which became known in 1962 as Profiles of the Future.

Among his predictions through the year 2100 was a "global library" in 2005.

Hmm... Wikipedia, anyone?

Clarke was smart, and well ahead of his time. Let's see how smart you are, given the answer!

Again, it could be wrong...

 

[sylas]

http://en.wikipedia.org/wiki/Arthur_C._Clarke" was a great author. What many don't know is that he was a very good inventor, as well as a statistics afficionado, his acclaim here, I suspect, as an auditor in the pensions section of the Board of Education (London Gazette: no. 34321, p. 5798, 8 September 1936. Retrieved on 2008-03-19.), although his interests along these lines may have been helped considerably with his Kings College degree in Mathematics he earned after the war.

Given: Everyone on a bus has an equal chance of having a birthday on any given day of the year.

Find: How many people must be aboard the bus for the odds of any single person having a birthday on today's date to be greater than 50%.

Ahh... Sounds easy! I know the answer, and in 1994, I actually worked out the proof, despite the fact that I was (and am still not) either a math or a statistics teacher.

So, my challenge to you is:

Post the Proof supporting your answer.

Hint: The answer is 23 (until I'm proven wrong).

Let n be the number of people, and let d be the number of days (365 or 366)

Number of ways of giving birthdays to all n people (in some order) is dⁿ

Number of ways of giving n different birthdays (in some order) is n!^dC_n = d!/(d-n)!

Hence the probability that all n people have different birthdays = d!/(d-n)!/dⁿ

The proof is completed by calculating for n = 22 and n = 23. Whether d is 365 or 366 still gives this as the dividing point.

I don't know any easier way.

Cheers -- sylas

 

[mugaliens]

You're along the right track, sylas, but the proof is in the pudding.

 

[sylas]

You're along the right track, sylas, but the proof is in the pudding.

I'm a mathematician. Mathematicians usually consider it enough to give sufficient details of the proof to show that the proof exists and that the publication contains enough information to carry the proof through to arbitrary levels of rigour. That's what I did above. Completing the proof is trivial and left as an exercise for the reader.

(There's a joke in that. Years ago a colleague of mine had that phrase made up into a rubber stamp he could put at the bottom of his discussion papers.)

Anyhow, since you want the proof.

Let Pr(n,d) be the probability that n independent uniformly distributed variables over a space of d distinct events end up having no two variables with the same value.

The previous post is a proof that Pr(n,d) = d!/(d-n)!/dⁿ.

You will note that for fixed d, this is a monotonically decreasing with n.

Now we calculate (to three figures of accuracy):
Pr(22,365) = 0.524
Pr(23,365) = 0.493

Ergo; for 22 or less people, you are more likely to have all of them with different birthdays, and for 23 or more you are more likely to have two or more with the same birthday.

QED.

I hate proofs that require a calculation like this; but it is a valid proof all the same.

Cheers -- sylas

 

[tyroman]

So, the number of passengers required for there to be a .5 probability that two of them have the same birthday is the same as the number required for a .5 probability that one of their birthdays is today?

from OP;
"Find: How many people must be aboard the bus for the odds of any single person having a birthday on today's date to be greater than 50%."

 

[Jimmy Snyder]

Completing the proof is trivial

Professor writes on the blackboard as he speaks and when he gets to a particular equation he says "This step is trivial". A student challenges the professor. "Are you sure it's trivial? I can't see it." The professor stares at the board silenty, absorbed in thought. After ten minutes he turns to the student and says "Yes, it's trivial."

 

[sylas]

So, the number of passengers required for there to be a .5 probability that two of them have the same birthday is the same as the number required for a .5 probability that one of their birthdays is today?

from OP;
"Find: How many people must be aboard the bus for the odds of any single person having a birthday on today's date to be greater than 50%."

Gagh. You're right! I actually thought of the classic birthday problem without reading the post sufficiently carefully. I was sucked in by the answer given of 23 which I know as the answer to the classic birthday problem.

The problem posted in the OP is also interesting and surprising.

The probability Pr(d,n) of n independently chosen values all not being a given day is (1-1/d)ⁿ.

So we require

$$\begin{array}{ll} & Pr(365,n) < 0.5 \\ \Rightarrow & (1-1/365)^n < 0.5 \\ \Rightarrow & n \log(1-1/365) < \log(0.5) \\ \Rightarrow & n > \log(0.5) / \log(1-1/365) = 252.65 \end{array}$$​

That is, you need 253 people on the bus before you have a better than even chance that one of them has their birthday today.

Cheers -- sylas

 

[glueball8]

Professor writes on the blackboard as he speaks and when he gets to a particular equation he says "This step is trivial". A student challenges the professor. "Are you sure it's trivial? I can't see it." The professor stares at the board silenty, absorbed in thought. After ten minutes he turns to the student and says "Yes, it's trivial."

Feynman - I still remember a guy sitting on the couch, thinking very hard, and
another guy standing in front of him, saying, "And therefore such-and-such
is true."
"Why is that?" the guy on the couch asks.
"It's trivial! It's trivial!" the standing guy says, and he rapidly
reels off a series of logical steps: "First you assume thus-and-so, then we
have Kerchoff's this-and-that; then there's Waffenstoffer's Theorem, and we
substitute this and construct that. Now you put the vector which goes around
here and then thus-and-so..." The guy on the couch is struggling to
understand all this stuff, which goes on at high speed for about fifteen
minutes!
Finally the standing guy comes out the other end, and the guy on the
couch says, "Yeah, yeah. It's trivial."
We physicists were laughing, trying to figure them out. We decided that
"trivial" means "proved."

 

[mugaliens]

Gagh. You're right! I actually thought of the classic birthday problem without reading the post sufficiently carefully. I was sucked in by the answer given of 23 which I know as the answer to the classic birthday problem.

The problem posted in the OP is also interesting and surprising.

Ahhh! Someone's paying attention!

That is, you need 253 people on the bus before you have a better than even chance that one of them has their birthday today.

This looks correct. Any other takers? How about the proof to the birthday probability?

How many people must be on the bus before the probability that two or more share the same birthday is greater than or equal to 50%?

 

[sylas]

Ahhh! Someone's paying attention!



This looks correct. Any other takers? How about the proof to the birthday probability?

How many people must be on the bus before the probability that two or more share the same birthday is greater than or equal to 50%?

Pay attention. It's in post #2, with the calculations in #4. The number is 23.

Cheers -- sylas

 

[mugaliens]

Ooops! My bad, sylas! I was reading further...