## You are here

Homebirthday problem

## Primary tabs

# birthday problem

The *birthday problem* is:
What is the probability of two or more people out of a group of $n$ do have the same birthday?

Solution. Let $A$ be the event two or more people out of a group of $n$ to have the same birthday. It is easy to find first the complement of $A$, $A^{c}$, which is that no two people out of a group of $n$ will have matching birthdays out of $365$ (number of days of one year) equally possible birthdays. We start with an arbitrary person’s birthday. So the second person’s birthday in order to be different from the first one gives us the probability, $1-\frac{1}{365}$. Consecutively, the third person’s birthday is different from the first two and we have $(1-\frac{1}{365})(1-\frac{2}{365})$. Finally for the the $n$th person’s birthday we get the probability

$\displaystyle P[A^{c}]$ | $\displaystyle=\left(1-\frac{1}{365}\right)\left(1-\frac{2}{365}\right)\dots% \left(1-\frac{n-1}{365}\right)$ |

$\displaystyle=\frac{(365-1)}{365}\frac{(365-2)}{365}\dots\frac{(365-(n-1))}{365}$ | |

$\displaystyle=\frac{(365-1)}{365}\dots\frac{(365-(n-1))}{365^{n}}$ | |

$\displaystyle=\frac{365!}{(365-n)!365^{n}}$ | |

$\displaystyle={365\choose n}\frac{n!}{365^{n}}$ |

By the last expression of the estimated probability we can see that there exists another easier approach to find the probability which is the following:

1. We set the possible ways for $1\dots n$ birthdays, $365^{n}$ as the denominator.

2. Using the binomial coefficient ${365\choose n}$, which represents the number of ways of picking $n$ unordered birthdays from $365$ days multiplied by the factorial $n!$ used for the number of orders, in that way we determine the numerator.

Therefore we have

$P[A^{c}]={365\choose n}\frac{n!}{365^{n}}$ |

whence

$P[A]=1-P[A^{c}]=1-{365\choose n}\frac{n!}{365^{n}}.$ |

The table below shows the probability $P[A]$ for some values of $n$

$n$ | $P[A]$ |
---|---|

$10$ | $0,11695$ |

$20$ | $0,41144$ |

$23$ | $0,50730$ |

$30$ | $0,70632$ |

$40$ | $0,89123$ |

$50$ | $0,97037$ |

## Mathematics Subject Classification

05A10*no label found*60C05

*no label found*60-00

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

## Comments

## 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.

Hope that answered your question.

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

approximately. See also the little table of "Birthday problem".

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.

## 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.

Then maybe it's worth copying over here?

Cam