La última pegatina es la que más cuesta

Completar un conjunto de N coleccionables toma mucho más que N intentos; los últimos elementos se esconden detrás de un muro de duplicados, y el valor esperado de paquetes es aproximadamente N·ln N.

Los duplicados hacen el daño: una vez que posees la mayor parte del conjunto, casi cada paquete repite algo que ya tienes, por lo que las últimas pegatinas cuestan más que todo el inicio del álbum.

Por el equipo editorial de Math Says Yes

Revisado por humanos según nuestros estándares de fuentes y corrección.

Cómo revisamos el contenido

LA TRAMPA

Planificamos con “N elementos, así que un poco más de N intentos” e ignoramos lo rápido que se acumulan los duplicados cerca del final.

Una cuadrícula casi completa de casillas coleccionables con un solo espacio vacío y una pila de duplicados.

Qué muestra esto

Recolectar cada elemento en un conjunto de N, donde cada intento te da un elemento aleatorio uniforme, no toma alrededor de N intentos. Toma aproximadamente N veces el logaritmo natural de N, más un pequeño término adicional de alrededor de 0.577 veces N. Para un conjunto de 50 elementos, eso da como resultado alrededor de 225 intentos en , más de cuatro veces el tamaño del conjunto en sí. La diferencia proviene enteramente de los duplicados: una vez que posees la mayor parte del conjunto, la abrumadora mayoría de las extracciones repiten algo que ya tienes, por lo que cada nuevo elemento único llega cada vez más lentamente.

Lo que muestran los números

100

200

400

pegatinas únicas

extracciones de una sola pegatina →

Para un conjunto de 50 elementos con 1 elemento por extracción, la mitad llega en unas 34 extracciones; la finalización promedia alrededor de 225.

Por qué la cola es brutal

Imagina que tienes N menos uno de los N artículos, con un solo espacio libre. Cada paquete es ahora el que necesitas con una de apenas 1 entre N, y todo lo demás es un duplicado; el costo se concentra al final. Una probabilidad de 1 en N significa que el número esperado de intentos para conseguir finalmente ese artículo es de aproximadamente N por sí solo. Así que el último artículo puede costar tantos intentos como miembros tiene todo el set. El penúltimo cuesta aproximadamente N sobre dos, el anterior aproximadamente N sobre tres, y así sucesivamente, que es exactamente de donde proviene el logaritmo en el total.

Por qué falla la intuición

La mayoría de la gente presupuesta mentalmente algo cercano a N intentos, tal vez un poco más, porque el set tiene N casillas y cada intento llena una casilla. Esa imagen asume silenciosamente que cada extracción es útil, pero las extracciones dejan de ser útiles a medida que el álbum se llena. Notamos la prisa inicial, cuando casi cada paquete añade una estampa, y olvidamos que esa misma aleatoriedad nos entregará duplicado tras duplicado más adelante. La brecha entre el N que esperamos y el N·ln N que realmente pagamos es toda la sorpresa, y crece con el tamaño del set.

Ejemplo práctico

Toma un álbum de estampas con 50 estampas distintas, en el que cada paquete es una al de manera uniforme. En , toma alrededor de 225 paquetes llenar todo el álbum. La primera mitad del álbum, las primeras 25 estampas, llega sorpresivamente rápido, en aproximadamente los primeros 34 paquetes. Después de eso, el ritmo colapsa. La estampa final promedia unos 50 paquetes por sí sola, y el último puñado en conjunto representa una gran parte del total. La gráfica esto: la línea se dispara al principio y luego se aplana en un arrastre largo y lento hacia la última casilla.

Cómo usarlo

Siempre que debas recolectar cada artículo de un set fijo y los artículos lleguen al , planifica para el final, no para el conteo. Establece tu presupuesto más cerca de N·ln N que de N, y espera que los últimos artículos dominen el esfuerzo. Mejor aún, intercambia. Intercambiar duplicados con otro coleccionista colapsa el final lento, porque tu excedente es exactamente el espacio vacío de alguien más. Por eso existe la cultura de intercambio de estampas: un mercado de comerciantes convierte el brutal final individual en uno colectivo rápido, y es la forma más barata de vencer las matemáticas.

En qué se equivocan las personas

Un coleccionista que tiene 40 de las 50 estampas de un álbum se siente completo en un 80%, pero solo ha gastado aproximadamente un tercio de los paquetes esperados. Presupuestar muy pocos intentos es el instinto con el que comienzas; este error viene después, a mitad de la colección: interpretar la proporción de artículos que posees como la proporción de esfuerzo gastado. La recolección aleatoria se concentra al principio: el progreso temprano es fácil porque muchos resultados ayudan, el progreso tardío es lento porque solo unos pocos lo hacen. El mismo número de artículos restantes puede ocultar una espera esperada mucho mayor.

Cuándo se aplica

El patrón del coleccionista de cupones aparece en álbumes de estampas, cajas de botín, pruebas de errores raros, búsqueda de todas las categorías en registros, recolección de respuestas de encuestas de cada segmento o visualización de cada variante en sistemas aleatorios. Se ajusta mejor cuando los resultados se muestrean aleatoriamente con reemplazo. El intercambio, la focalización o las desiguales cambian la espera.

Nota sobre la fuente

El tratamiento autorizado del problema del coleccionista de cupones es el de Wolfram MathWorld. La página utiliza el resultado formal como intuición: el tiempo esperado está impulsado por la búsqueda cada vez más lenta de las últimas categorías no vistas.

Pruébalo

Coleccionista de cupones

Abre sobres y observa cómo los últimos adhesivos tardan en salir.

% completado

sobres abiertos

se espera terminar

Los primeros adhesivos llegan rápido, pero cerca del final casi todos los sobres son repetidos; solo el último artículo requiere tantos sobres como artículos tiene toda la colección.

Preguntas frecuentes

¿Por qué es tan difícil conseguir el último artículo de una colección?

Porque una vez que falta un solo artículo en un set de N, cada extracción aleatoria es la que necesitas solo con una probabilidad de 1 entre N. Esa pequeña probabilidad significa que la espera esperada para ese artículo final es de aproximadamente N intentos por sí sola.

¿Cuántos paquetes se necesitan para terminar un set de N artículos?

En promedio, alrededor de N veces el logaritmo natural de N, no N. Para un set de 50 artículos, eso es aproximadamente 225 paquetes, más de cuatro veces el tamaño del set, porque los duplicados dominan las extracciones posteriores.