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.

Thanks for any help one can give with this…

I need a general equation for the following problem, and I am sure it’s a special case of Poisson or binomial or Bernoulli or something, but I can’t seem to rearrange the equations to get the answer I need.

I have:

  • N objects where:

  • A pool of barcodes of size X, where the barcode is assigned randomly for each object from a range of 1 to X barcodes.

  • There is no “memory” of what barcodes were last assigned, and there is no depleting of barcodes, so the pool of barcodes is “replenished” for each assignment of a barcode to an object.
  • Each object gets only one barcode.

The question: What is the range size of barcodes (1 to X) that ensures that there is a given confidence that no two or more objects are tagged with the SAME barcodes ?

My objective is to make the library of barcodes as SMALL as possible to ensure I don’t repeat barcodes on objects with a given confidence.

share|improve this question
2  
Questions like this are analyzed in computer science, see Hash table or Birthday attack, ... –  Fabian Aug 18 '12 at 3:33
add comment

2 Answers

You can't ensure uniqueness, but you can make the probability of a collision as small as you like.

For $n$ objects, if you want to reduce the probability of a collision to only $p$, you need to select from this many different barcode numbers: 1 and $$-n^2 \over 2 \log (1-p)$$ where as usual $p$ is between 0 and 1.

For example, suppose you have $n=64$ and you want a one-in-twenty ($p=0.05$) chance of a collision, so you get ${-64^2 \over 2 \log 0.95 } = 39,927$; call it 40,000. To reduce the chance of a collision to one in a million, take $p=0.000001$, and the formula gives $2,047,998,976$, so a bar code of ten random decimal digits is plenty. To handle ten times as many objects, use one hundred times as many barcode numbers. (That is, make the barcodes two digits longer.)

With $n=23$ and a $p=\frac12$ chance of a collision, we get 381, which accords well with the usual statement of the birthday paradox—in that example we are usually selecting numbers between 1 and 365 (or 366) and we find that there is around a 50% chance of collision with 23 people.

(The logarithm here is to the base $e$. If the minus sign in the formula is puzzling you, note that $\log(1-p)$ is always negative.)

Ross Millikan already referred you to the relevant wikipedia article, but it is somewhat long, so you may want to pay special attention to the section titled "Cast as a collision problem".

share|improve this answer
    
perfect-- thanks. So, what if I cast the problem slightly differently... given n objects, and X barcodes-- how many SETS of objects should I expect to have a collision. –  user38147 Aug 18 '12 at 6:25
    
Ahh, I think I answer my own question looking on the same wiki page under collision counting. n-d + d(d-1/d)^n –  user38147 Aug 18 '12 at 7:00
add comment

As a rough heuristic, you have $\frac {N^2}2$ pairs of barcodes that might match. You need somewhat more than that to likely avoid collision. For more information, you might see Wikipedia on the generalized birthday problem. But in most applications of this, you have a rough idea of $N$, so factors of $e$ don't matter.

share|improve this answer
    
Perfect. Got it. –  user38147 Aug 18 '12 at 3:48
    
@user38147 Note that if you pick from $N^2\over 2$ bar codes for $N$ objects, you will get around a 63% chance of a collision. "Somewhat more" is crucial here. –  MJD Aug 18 '12 at 4:56
    
@MarkDominus: That was the point of my saying that factors of $e$ don't matter here. Your calculation is correct and useful, but if you only know $N$ within a factor 3 (10?, 100?) you need to allow enough margin. Practical factors come in here-the real difference is between 32 bits and 64, not 28 and 29. –  Ross Millikan Aug 18 '12 at 5:17
    
I posted this to Mark Dominus above, but I don't know how this forum works if everyone who commented in a thread is notified, so I am posting to Ross as well: So, what if I cast the problem slightly differently... given n objects, and X barcodes-- how many SETS of objects should I expect to have a collision? –  user38147 Aug 18 '12 at 6:36
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.