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.

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

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
Thanks, this has definitely given me a push in the right direction. My only concern is whether this holds true where the events are independent, but not all equally likely e.g. from the birthday example, higher birth rates resulting from Valentine's day and new year's eve. –  Reuben John Pengelly Jan 4 '13 at 15:31
    
@ReubenJohnPengelly: It doesn't matter. The variation in likeliness goes into the calculation of $q$, but then it goes through. If you had one event that was probability $\frac 12$ and $500$ events with probability $\frac 1{1000}$, then $q=(\frac 12)^2+500(\frac 1{1000})^2$ for example. –  Ross Millikan Jan 4 '13 at 15:45
    
Thanks for the clear explanations, it all makes sense to me now. My only final question is do you have a source for this at all? I can find very little on birthday paradox with unequal probabilities in the literature. As this is hopefully for inclusion in a paper then I would of course need to be able to justify my use of this. Many thanks again. –  Reuben John Pengelly Jan 7 '13 at 15:22
    
@ReubenJohnPengelly: No, I have no source for it. It is a certain amount of a handwave, because you assume one pair matching is independent of any other pair matching. When the probability of a match is small, this will be close. It sounds like for your use it is no problem-do you really care if the probability of a collision is 0.005 instead of 0.003? At that level it is a simple calculation. –  Ross Millikan Jan 7 '13 at 15:25
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.