N needed for probability > .001 of two people being a match at six genetic markers? If for each marker there is a 1/9 chance that any two people are a match, how large would the sample need to be for the probability to exceed .001 that two people are a match at six markers?
 A: This is the celebrated "birthday problem": How many people must be randomly chosen from a population in order that the probability is at least $1/2$ that some pair among them have the same birthday (assuming, not so realistically, that all $365$ dates are equally probable and that we exclude those born on the 29th of February for the sake of simplicity)?
I'm construing the question as referring to the probability that somewhere among the sample there are two that match.
This is one of those problems most easily solved by asking what is the probability that the event in question does NOT happen.
The probability that two persons match at six markers is $1/9^6.$ The probability that they don't is $1 - (1/9^6).$ Among $N$ persons, the probability that no two match is
\begin{align}
& \Pr(\text{2nd doesn't match 1st}) \\[8pt]
{} \times {} & \Pr(\text{3rd doesn't match first 2} \\
& \qquad\qquad\text{given that the first 2 don't match}) \\[8pt]
{} \times {} & \Pr(\text{4th doesn't match first 3} \\
& \qquad \text{given that no two among the first 3 match}) \\[8pt]
{} \times {} & \cdots\cdots \\[10pt]
= {} & \left(1 - \tfrac 1 {9^6} \right) \times\left( 1 - \tfrac 2 {9^6} \right) \times \left( 1 - \tfrac 3 {9^6} \right) \times\cdots\times\left( 1 - \tfrac {N-1} {9^6} \right).
\end{align}
One way to proceed from here is brute-force computation: compute this for successive values of $N$ until it is no more than $1-0.001.$
I think there may also be an intelligent to do go on from there; maybe I'll see if I can find it.
(Here I assumed that the events that you and I match at different markers are nine independent events. Whether they are independent is something you haven't said anything about.)
A: An approximation seems appropriate here.
Assuming independence of matching different markers, the probability that any two people match six markers is $(1/9)^6$.  If there are $n$ people in the sample, there are $\binom{n}{2}$ pairs.  If we define a success as two people matching six markers, then the expected number of successes is
$$\lambda = \binom{n}{2} \left( \frac{1}{9} \right)^6$$
The events that different pairs of people match on all six markers are not independent, so the total number of successes does not have a Binomial distribution.  But the events are "approximately" independent, so as an approximation we might assume that the total number of matches has a Binomial distribution.  And for small probabilities the Binomial distribution is approximately Poisson, so we might as well go all the way and assume the total number of matches is Poisson with parameter $\lambda$.  With that assumption, if $X$ is the total number of successes then
$$P(X \ge 1) = 1- P(X=0) = 1-e^{-\lambda}$$
We want $P(X \ge 1) \ge 0.001$, which is equivalent to $P(X=0) \le 0.999)$.  So we have the equivalent inequalities
$$e^{-\lambda} \le 0.999$$
$$\lambda \ge -\ln(0.999)$$
$$\binom{n}{2} \left( \frac{1}{9} \right)^6 \ge -\ln(0.999)$$
Either by trial and error or by solving a quadratic equation, we find that the least $n$ that satisfies the final inequality is $n= 34$, which results in $P(X \ge 1) \approx 0.0011$.
