# birthday problem

## Primary tabs

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

## Mathematics Subject Classification

05A10 Factorials, binomial coefficients, combinatorial functions
60C05 Combinatorial probability
60-00 General reference works (handbooks, dictionaries, bibliographies, etc.)

### How many needed

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

### Re: How many needed

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.

James

### Re: How many needed

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.

### Re: How many needed

I don't believe the answer 19. I calculated elementarily that
P(at least two out of 25 have common birthday) = 0,5687
Jussi

### Re: How many needed

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.

### Re: How many needed

The expected value doesn't answer the original question.

### Re: How many needed

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

### Re: How many needed

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.

### Re: How many needed

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.

### Re: How many needed

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

### Re: How many needed

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

### Re: How many needed

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.