Fork me on GitHub
Math for the people, by the people.

User login

birthday problem

Synonym: 
birthday paradox
Type of Math Object: 
Definition
Major Section: 
Reference
Groups audience: 

Mathematics Subject Classification

05A10 no label found60C05 no label found60-00 no label found

Comments

How many people are needed in a group for that it were more probable that at least two have the same birthday than that all have distinct birthdays?
Jussi

Given N possibilities, you need at random \sqrt{N} samples to have a probability of 1/2 of any duplicate. In the birthday problem the N is the number of days in a year, so 365. So you need \sqrt{365}=19 to have a 50% chance of a duplicate.

This is the same trick used in the Pollard -\rho tests for factorization. It is neat to see such an elementary result used on such a hard problem with positive outcomes.

Hope that answered your question.

James

Something does not see right here.
The table in the entry shows for 20 people a probability of .41
for a duplicate. So the answer ought to exceed 20.

i checked Feller's book An Introduction to Probability Theory
and its applications, vol I, 2nd ed. c 1957
and he has a problem (pag 224, problem 18 and 19) to find the n
so that the expected number of multiple birthdays in a group of
n people exceeds 1. His answer is n>=28.

I don't believe the answer 19. I calculated elementarily that
P(at least two out of 25 have common birthday) = 0,5687
approximately. See also the little table of "Birthday problem".
Jussi

Ooops, I forgot there is a constant, the birthday problem is O(\sqrt{N}) but the constant is required! Thanks for spotting that. The constant is 1.2, so 1.2\sqrt{365}=23.

Thanks Mathprof and Jussi.

The expected value doesn't answer the original question.

Algeboy, I don't believe that 23 suffices =o)

Well perhaps I don't understand what you were asking for, but this number is very well researched, google it, maybe try:

http://www.npr.org/templates/story/story.php?storyId=4542341

It is a very well used result in probabilistic attacks on hard number theory problems and in cyptography, which is the only reason I have any knowledge of the result.

Suppose there are 365 days in a year and suppose you need x people to find two matching birthdays (not including year). The complement of this is that none of the x people have matching birthdays. There are 365 choices of birthdays for the first person picked, 364 choices remain for the 2nd person picked, etc... So the total number of choices for all x people having mutually distinct birthdays is

A(x) = 365*364*...*(365-x+1)

But there are

B(x) = 365^x

choices if we allow duplicate birthdays.

So the probability that at least two people have the same birthday is p(x) = 1 - A(x)/B(x). So we want to find the least positive integer x such that p(x)>= 0.5. Use a calculator or a spreadsheet application you find that x is 23.

Now I believe that 23 persons suffice -- I calculated the corresponding probability (it is approx. 0,5073).

Hi Algeboy, I don't know your square-root method. Can you please explain it -- perhaps in a little entry?
Jussi

I've added an entry to this article to explain the approximation. It is crude as you will see but it works. Wikipedia actually has a really nice page on this I discovered.

> I've added an entry to this article to explain the
> approximation. It is crude as you will see but it works.
> Wikipedia actually has a really nice page on this I
> discovered.

Then maybe it's worth copying over here?

Cam

Subscribe to Comments for "birthday problem"