Lección
Completar un conjunto toma más tiempo de lo que crees
Rellenar los últimos elementos de una colección cuesta mucho más que los primeros, porque los duplicados se acumulan hacia el final.
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 regla de n·ln n
Se siente natural asumir que recolectar n elementos diferentes toma aproximadamente n intentos. No es así. Cuando cada intento te da un elemento aleatorio uniforme, completar el conjunto toma alrededor de n veces el logaritmo natural de n. Para un conjunto de 50, eso es alrededor de 225 intentos, no 50. La razón es que sigues extrayendo elementos que ya posees. Al principio, casi todas las extracciones son nuevas, por lo que el recuento sube rápidamente, pero el progreso se desacelera bruscamente a medida que el conjunto se llena, porque la de extraer algo que falta sigue disminuyendo. Cuanto mayor es el conjunto, peor se vuelve esta brecha entre n y n·ln n.
La cola cruel
El final es donde se esconde el costo. Supongamos que tienes todos menos uno de los n elementos. Cada extracción ahora es el elemento faltante solo con una de 1 entre n, y cualquier otra cosa es un duplicado. La cantidad de intentos que necesitas se desprende de esa única probabilidad: en toma alrededor de n extracciones solo para conseguir ese elemento final. Así que en un conjunto de 50 elementos, el último cromo por sí solo promedia alrededor de 50 sobres, mientras que la primera mitad del conjunto llegó en una pequeña fracción de eso. La cola no es un detalle de redondeo. Es el tramo más caro de todo el esfuerzo, y es exactamente la parte que nuestra planificación tiende a ignorar.
Por qué el intercambio gana
Si los duplicados hacen que la cola sea costosa, deshacerse de los duplicados la abarata. Cuando intercambias un elemento repetido con otro coleccionista que lo necesita por uno que te falta, colapsas la parte lenta del problema. Dos coleccionistas que intercambian sus repuestos se saltan la espera castigadora por los pocos elementos raros, porque tu excedente es el vacío de otro y viceversa. Esta es la matemática detrás de la cultura del intercambio de cromos: la tradición escolar de intercambiar duplicados no es solo social, es la forma más efectiva de vencer el costo n·ln n. Un mercado de comerciantes convierte una cola individual brutal en un final colectivo rápido.
Dónde aparece
La misma forma aparece mucho más allá de los álbumes de cromos. Las cajas botín y los juegos gacha otorgan recompensas aleatorias, por lo que completar una lista de personajes o cartas choca exactamente con esta cola, lo cual es parte de por qué los últimos son tan frustrantes de perseguir. Las pruebas de software también se encuentran con esto: si un programa tiene muchos caminos de código raros y tus entradas los alcanzan al , cubrirlos todos lleva mucho más tiempo de lo que sugiere el recuento de caminos, y la última rama no probada puede ser obstinadamente difícil de activar. Siempre que necesites cada elemento de un conjunto fijo y los recolectes al azar, espera que la línea de meta esté mucho más lejos de lo que implica el tamaño del conjunto por sí solo.
Preguntas frecuentes
¿Un conjunto más grande se vuelve desproporcionadamente más difícil de terminar?
Sí. La completitud escala con n veces ln n en lugar de n, por lo que duplicar el tamaño del conjunto más que duplica los intentos que necesitas en promedio. El factor logarítmico crece con n, por lo que las colecciones grandes se sienten tan castigadoras cerca del final.
¿Por qué intercambiar duplicados ayuda tanto?
Porque los duplicados son precisamente lo que hace que la cola sea costosa. Intercambiar tus repuestos por elementos que te faltan elimina la larga espera por las piezas raras faltantes, ya que tu excedente llena el vacío de otro coleccionista y el de ellos llena el tuyo. Un mercado de intercambio convierte un final individual lento en uno compartido rápido.
Prueba la idea
Coleccionista de cupones
Abre sobres y observa cómo los últimos adhesivos tardan en salir.
0%
% completado
0
sobres abiertos
91
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.
Comprobación rápida
Tienes 49 de 50 pegatinas. Con 1 pegatina aleatoria por sorteo, ¿cuántos sorteos más faltan para conseguir la última, en promedio?
A
Unos 50 sorteos.
B
Unos 2 sorteos.
C
Unos 5 sorteos.