Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a room with many people, we ask each person his/her birthday. Let $N$ be the number of people queried until we get a "duplicate" birthday. Calculate $\mathbb{P}(N >n)$ for $n = 0,1,2,\dots$.

The solutions says

$$\mathbb{P} (N>n) = \displaystyle\frac{365}{365} \frac{364}{365} \dots \frac{365-n+1}{365}$$

I am curious to know how to achieve the answer? Thanks!

share|improve this question
    
Are you sure that the answer is requested for $n = 0$? Because your formula seems to gives a probability exceeding $1$ for $n = 0$ (it does depend on how one interprets the product). For $n = 1$, it is $\frac{365}{365}$ which is correct: you must ask more than one person in order to have a duplicate birthday. –  Dilip Sarwate Sep 18 '12 at 17:53
    
No, it doesn't. The solution is a product of $n$ factors, hecne the empty product with value 1 for $n=0$. –  Hagen von Eitzen Sep 18 '12 at 17:57
    
Note that $N>n$ if and only if the first $n$ people queried have distinct birthdays. –  David Mitra Sep 18 '12 at 18:02
add comment

2 Answers

up vote 3 down vote accepted

The chance that you have to ask more than 1 is clearly $1=\frac {365}{365}$ as the first person can't match. The chance that you have to ask more than 2 is $\frac {364}{365}$, as there is only one day to match. The third person has two chances to match, as we have been told that the first two are different, and so on.

share|improve this answer
add comment

This problem is called birthday paradox. It is acutally a very interesting problem. In a group of $23$ people the probability that two of them will have exactly the same birthday is one half. If you think that there are $365$ days and $23$ people such a probability $p=0.5$ sounds a bit high perhaps.. though it is the probability..

There is also a very good exponential approximation to the problem. This problem is taught in cryptography lectures as it is important to know the probability of collisions if one wants to design some hash functions.

For more informations I think wiki will be quite enough:

http://en.wikipedia.org/wiki/Birthday_problem

What Wiki says about hash functions (if interesting):

In an ideal "perfect hash function", no bucket should have more than one record; but a small number of collisions is virtually inevitable, even if n is much larger than m – see the birthday paradox).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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