# Calculating the probability of the Nth sample in the birthday problem w/o knowing the previous samples

If we draw two random variates from a discrete uniform distribution $[1, D]$, the probability that the samples are distinct is $(D-1)/D$. Explanations of the birthday problem state that if we sample a third time, the probability that this third sample is distinct from the first two is $(D-1)(D-2)/D^2$. Doesn't this assume that the first two samples were distinct? If they are not distinct, then the probability that the third sample is distinct is $(D-1)/D$. The solution to the birthday problem requires us to know the probability that the $n^\textrm{th}$ random variate is distinct from the previous samples. How can we calculate the probability that the $n^\textrm{th}$ sample is distinct from the previous samples without knowing the values of these previous samples?

• Welcome to the site, @Dan. Is this homework? If it is, you need to add the 'homework' tag. – gung Oct 13 '12 at 21:11
• @gung This is not homework, it is for my own edification. I saw the problem in David Mackay's textbook on information theory and was not satisfied with his explanation (or other similar explanations on the net). – Dan Oct 13 '12 at 21:13

In the usual context of the birthday problem, if the first two values are not distinct the problem is solved and the third and subsequent values are irrelevant. What is confusing here is that you have written

Explanations of the birthday problem state that if we sample a third time, the probability that this third sample is distinct from the first two

What is really meant here (and is a big part of the unintuitive nature of the birthday problem), is "the probability that this third sample is distinct from the first two, given that they are distinct from each other".

The probability all $3$ are distinct is $\frac{(D-1)(D-2)}{D^2}$.

The probability the third is not equal to the first two is $\frac{(D-1)^2}{D^2}$. Imagine choosing $C$ first. Then there are $D-1$ choices for $A$ so that $A\ne C$, and $D-1$ choices for $B$ so that $B\ne C$.

If you are given that the first two are distinct, the conditional probability that the third is different from both is $\frac{D-2}{D}$.

You are correct that if you are given the first two are equal, the conditional probability that the third is different is $\frac{D-1}{D}$.

If $D=10$, these are $72\%, 81\%, 80\%,$ and $90\%,$ respectively. The $81\%$ is naturally a weighted average between $80\%$ and $90\%$, weighted by the probabilities that the first two are distinct or not. The $72\%$ can also be viewed as a weighted average between $81\%$ and $0$, weighted by the conditional probability that the first two are distinct from each other given that they are distinct from the third.

• Because this post has been upvoted, SE construes its deletion as removing potentially useful information; I have therefore undeleted it. – whuber Mar 30 '13 at 15:05