¿Qué tan grande debe ser una biblioteca de códigos de barras para garantizar la singularidad?

Question

Gracias por cualquier ayuda que se pueda dar con esto ...

Necesito una ecuación general para el siguiente problema, y estoy seguro de que es un caso especial de Poisson o binomial o Bernoulli o algo así, pero no puedo parecer a reorganizar las ecuaciones para obtener la respuesta que necesito.

Tengo:

• N objetos donde:

• Un conjunto de códigos de barras de tamaño X, donde el código de barras se asigna aleatoriamente para cada objeto de un rango de 1 a X códigos de barras.

• No hay "memoria" de qué códigos de barras se asignaron la última vez, y no hay agotamiento de códigos de barras, por lo que el conjunto de códigos de barras se "reabastece" para cada asignación de un código de barras a un objeto.

• Cada objeto recibe solo un código de barras.

La pregunta: ¿Cuál es el rango de tamaño de códigos de barras (1 a X) que garantiza que haya una confianza dada de que ningún dos o más objetos estén etiquetados con los mismos códigos de barras?

Mi objetivo es hacer que la biblioteca de códigos de barras sea lo más PEQUEÑA posible para garantizar que no repita códigos de barras en objetos con una confianza dada.

Answer 1

No puedes asegurar la singularidad, pero puedes hacer que la probabilidad de una colisión sea tan pequeña como desees.

Para $n$ objetos, si deseas reducir la probabilidad de colisión a solo $p$, necesitas seleccionar esta cantidad de números de código de barras diferentes: 1 y $$-n^2 \over 2 \log (1-p)$$ donde como de costumbre $p$ está entre 0 y 1.

Por ejemplo, supongamos que tienes $n=64$ y deseas una probabilidad de una en veinte ($p=0.05) de una colisión, entonces obtienes ${-64^2 \over 2 \log 0.95 } = 39,927$; redondeado a 40,000. Para reducir la probabilidad de una colisión a una entre un millón, toma $p=0.000001$, y la fórmula te dará $2,047,998,976$, por lo que un código de barras de diez dígitos decimales aleatorios es suficiente. Para manejar diez veces más objetos, utiliza cien veces más números de código de barras. (Es decir, haz que los códigos de barras sean dos dígitos más largos.)

Con $n=23$ y una probabilidad de colisión de $\frac12$, obtenemos 381, lo cual concuerda bien con la afirmación habitual del paradigma del cumpleaños—en ese ejemplo solemos seleccionar números entre 1 y 365 (o 366) y descubrimos que hay alrededor de un 50% de probabilidad de colisión con 23 personas.

(El logaritmo aquí es en base $e$. Si el signo negativo en la fórmula te desconcierta, ten en cuenta que $\log(1-p)$ siempre es negativo.)

Ross Millikan ya te ha remitido al artículo relevante de Wikipedia, pero es algo largo, por lo que quizás quieras prestar especial atención a la sección titulada "Cast as a collision problem".

Answer 2

Como regla general, tienes $\frac {N^2}2$ pares de códigos de barras que podrían coincidir. Necesitas algo más que eso para evitar probablemente colisiones. Para obtener más información, puedes ver Wikipedia sobre el problema del cumpleaños generalizado. Pero en la mayoría de las aplicaciones de esto, tienes una idea aproximada de $N$, así que los factores de $e$ no importan.