Calculating the probability of any event in a set occuring at least twice in a large sample.

Question

Firstly apologies for lack of maths skill, I am a biologist and sadly fit the stereotype of being terrible at maths.

I am designing a set of unique identifiers for sample identification, which are generated from the genetic data associated with the sample.

I am trying to calculate the probability that within a given population of samples, two or more samples will be assigned the same identifier, which clearly is not desirable.

The identifiers are an ordered concatenation of $22$ pieces of data, each with three states i.e. RR, RA & AA. These three states each have a different frequency in the population, as well as being different between the 22 pieces of data. I think that for these 22 pieces of data the number of possible identifiers will be $3^{22}$ =~ $3.14x10^{10}$. Presumably the average probability for each identifier would be $\large \frac{1}{3.14x10^{10}}$, but it would be the upper outliers that would be the limiting factor on the use of the method.

I have calculated the probability of the most probable identifier occurring in a single sample, which is ~$2x10^{-7}$. As such, I think that:

$p$ = $(2x10^-7)^{2}$ $\cdot n$

where p is the probability of the most likely identifier being assigned twice and n is the number of samples in the population.

This is as far as my maths can take me, though this clearly fails say where the identifier can be assigned more than twice, and as there are $3.14x10^{10}$ identifiers which could potentially also be repeatedly assigned.

I am struggling to see a way to deal with the multiple identifiers issue other than presuming that all identifiers have the same probability as this most likely identifier, though this would surely result in an enormously conservative estimate.

Once I have a way to do this I will then try to calculate the maximum size of a population sampled while maintaining a probability of replication of less than say $0.05$.

Any help with this would be greatly appreciated, sorry for the rather cumbersome explanation. I and others in my group have some skill in programming, so computational approaches that are more accurate are viable, and indeed preferable to conservative estimations.

Many thanks

Answer 1

This is an example of the birthday problem. it sounds like you can calculate the chance $q$ that one specific pair matches. Then a close approximation is that for $N$ samples is that there are $\frac 12N(N-1)\approx \frac {N^2}2$ pairs. The chance of no match is then about $(1-q)^{\frac {N^2}2}$, which for low chances is about $1-\frac {qN^2}2$, so your chance of a match is about $\frac {qN^2}2$. This will be quite accurate if the chance of a match is small, which is what you want.