Si alguna vez has coleccionado las pegatinas que vienen en las bolsas de aperitivos, seguramente recuerdas que al principio encontrabas una nueva cada vez que abrías una bolsa y pensabas que completarías la colección enseguida. Pero, cuando el álbum está casi lleno, empiezas a encontrar una y otra vez las que ya tienes, y las últimas una o dos apenas aparecen. Esto se debe a cómo funcionan las probabilidades, no a la mala suerte. El «problema del coleccionista de cupones (Coupon Collector's Problem)» describe matemáticamente este fenómeno.
Dicho de forma sencilla, el problema del coleccionista de cupones plantea una pregunta de probabilidad. Si en cada extracción sale al azar uno de varios tipos, ¿cuántas extracciones hacen falta en promedio para conseguir al menos un ejemplar de cada tipo? La cifra es mucho mayor de lo que cabría imaginar, y la mayor parte de esas extracciones se dedica a esperar los últimos tipos.
En este artículo veremos en qué consiste el problema del coleccionista de cupones, cómo se calcula el número medio de extracciones, qué muestran algunos ejemplos numéricos concretos y, por último, dónde se aplica este problema en la vida cotidiana y en la tecnología, y qué conviene tener en cuenta.
El último cupón es el que más cuesta en el problema del coleccionista de cupones
¿Qué es el problema del coleccionista de cupones?
El nombre del problema procede de las promociones en las que se incluía un cupón en cada caja de cereales y se entregaba un premio a quien reuniera todos los tipos. El modelo matemático parte de las siguientes condiciones.
(1) El número de tipos es fijo
Hay n tipos de cupones por coleccionar y el coleccionista conoce de antemano ese número.
(2) En cada extracción sale un cupón al azar
Cada vez que se compra una caja, sale uno de los n tipos, todos con la misma probabilidad. Lo que haya salido antes no influye en el resultado siguiente.
(3) Pueden salir cupones repetidos
Puede volver a salir un cupón que ya se tiene. Recibir varias veces el mismo cupón es lo que alarga la colección.
En términos de un dado, equivale a preguntar cuántas veces hay que lanzarlo en promedio hasta que hayan salido sus seis caras al menos una vez cada una.
¿Cómo se calcula el número medio de extracciones?
El cálculo se simplifica si dividimos la colección en etapas, cada una de las cuales dura hasta que se consigue un tipo nuevo.
(1) Al principio, cualquier cupón es nuevo
Cuando aún no se tiene ningún cupón, la primera extracción siempre da un tipo nuevo, así que basta con una sola.
(2) Cuantos más tipos se tienen, menor es la probabilidad de obtener uno nuevo
Si ya se tienen k tipos, la probabilidad de obtener uno nuevo es (n - k) / n. Si se repite un intento con probabilidad de éxito p hasta conseguir el primer éxito, hacen falta en promedio 1 / p intentos. Por lo tanto, esta etapa requiere en promedio n / (n - k) extracciones.
(3) Se suman todas las etapas
Al sumar los promedios de cada etapa, el promedio total es n × (1 + 1/2 + 1/3 + … + 1/n). La suma entre paréntesis se llama número armónico. A medida que n crece, el promedio total aumenta hasta situarse aproximadamente en n × (logaritmo natural de n) + 0.577 × n. El matemático francés Pierre-Simon Laplace también trató este problema en su obra sobre teoría de la probabilidad de 1812.
El cálculo se entiende mejor con un dado. En promedio, se necesitan 1 lanzamientos para obtener la primera cara, 6/5 para obtener la segunda cara distinta, 6/4 para la tercera, 6/3 para la cuarta, 6/2 para la quinta y 6/1 para la sexta y última. La suma es de unos 14.7 lanzamientos, de los cuales un promedio de 6 se dedica solo a esperar la última cara.
Como muestra la fórmula, la última etapa, cuando falta un solo tipo, requiere por sí sola un promedio de n extracciones. Cuantos más tipos se han reunido, más difícil resulta encontrar uno nuevo, y eso alarga el proceso de completar la colección.
Lo que muestran las cifras sobre las colecciones
Los resultados concretos muestran hasta qué punto los cálculos difieren de lo que sugiere la intuición.
- Para ver las seis caras de un dado (Die), como calculamos antes, hay que lanzarlo unas 14.7 veces en promedio. Podría parecer que bastan seis lanzamientos, pero hacen falta más del doble.
- Con 10 tipos de cupones (Ten Coupons), se necesitan unas 29.3 extracciones en promedio.
- Con 50 tipos de cupones (Fifty Coupons), se necesitan unas 225 extracciones en promedio. Para reunir los primeros 25 tipos bastan unas 34 extracciones, mientras que reunir los 25 restantes requiere unas 191.
- Con 100 tipos de cupones (One Hundred Coupons), el promedio es de unas 519 extracciones, más de cinco veces el número de tipos.
Estas cifras son promedios, así que en la práctica muchas personas tardan bastante más. Además, si hay «cartas raras» de las que se incluyen deliberadamente menos ejemplares, el número esperado de extracciones supera al del caso en que todos los tipos tienen la misma probabilidad.
Aplicaciones del problema del coleccionista de cupones y aspectos que conviene tener en cuenta
Este problema se aplica en diversos ámbitos más allá de los álbumes de pegatinas.
(1) Promociones y diseño de estrategias de consumo
Los artículos coleccionables que salen al azar están diseñados para que se compre el mismo producto repetidamente con el fin de conseguir los últimos tipos. Para los consumidores, el simple hecho de calcular de antemano el coste esperado puede reducir las compras impulsivas.
(2) Informática y algoritmos
Este cálculo se utiliza para determinar cuánto se tarda en recorrer todos los casos al menos una vez al elegir elementos al azar. Los libros de texto sobre algoritmos aleatorizados lo presentan como un ejemplo clásico.
(3) El intercambio puede ser la solución
Cuando varias personas coleccionan juntas e intercambian sus repetidos, cada una tiene que comprar mucho menos que si coleccionara por su cuenta. Un ejemplar que le sobra a una persona puede ser justo el que le falta a otra.
(4) Una forma de estimar cuántas extracciones faltan
Si ya has reunido varios tipos, puedes aplicar el mismo cálculo solo a los que te faltan. Por ejemplo, si de un total de 50 tipos ya has reunido 49, necesitarás en promedio 50 extracciones más para conseguir el último cupón.
En los productos reales, las probabilidades suelen variar según el tipo o no se hacen públicas, así que conviene tomar el cálculo como punto de partida.
El problema del coleccionista de cupones muestra cuánto influye un hecho sencillo. A medida que aumenta la colección, cuesta más conseguir un tipo nuevo. Si el último cupón tarda especialmente en salir, es por cómo funcionan las probabilidades, no por mala suerte.
Calcular cuántas extracciones harán falta y buscar amigos con quienes intercambiar los repetidos son el primer paso para coleccionar con sensatez.
