Esta es una traducción automática y el texto original está en inglés. Leer el original
Veintitrés personas y la coincidencia que cabe esperar
Veintitrés personas forman 253 parejas. Nadie calcula jamás esas 253, y esa es la única razón por la que la respuesta parece errónea.
Si se reúnen 23 personas en una sala, la probabilidad de que dos de ellas compartan cumpleaños es del 50,7 %. Con 70 personas es del 99,9 %.
Casi todo el mundo estima una cifra muy superior, y la razón es que se plantea la pregunta equivocada. El instinto lleva a pensar en uno mismo: ¿cuál es la probabilidad de que alguien aquí comparta mi cumpleaños? Se trata de un suceso mucho más raro, y se necesitarían unas 253 personas para que superase la mitad.
La pregunta real se refiere a cualquier pareja. Y las parejas no escasean.
Contar parejas, no personas
Veintitrés personas forman 23 × 22 ÷ 2 = 253 parejas distintas. Cada pareja tiene una probabilidad de 1 entre 365 de coincidir. El número de parejas crece con el cuadrado del número de personas, por lo que duplicar el aforo de la sala cuadruplica las oportunidades de que se dé una coincidencia.
El cálculo exacto se efectúa a la inversa: la probabilidad de que ninguna pareja coincida, que es 365/365 × 364/365 × 363/365 × … para 23 términos, dando 0,493. Uno menos eso da 0,507.
La regla general que conviene recordar
Para N posibilidades igualmente probables, se necesitan aproximadamente √N extracciones antes de que una repetición sea más probable que lo contrario. Para los cumpleaños, √365 ≈ 19, y la constante resulta ser de aproximadamente 1,18 × √N ≈ 22,5. Lo bastante cerca de 23.
Raíz cuadrada, no la mitad. Ese es el número en el que la gente se equivoca, y el error va en la dirección de suponer que las coincidencias son más raras de lo que son en realidad.
Donde deja de ser un truco de salón
Colisiones hash. Una tabla hash con mil posiciones no empieza a registrar colisiones cuando se aproxima a mil entradas. Empieza a colisionar en torno a las treinta. Por eso las implementaciones de tablas hash se ocupan de la gestión de colisiones desde la primera inserción, y por eso medir únicamente el factor de carga ofrece poca información sobre cuántos sondeos requiere una búsqueda. La herramienta Hash Table muestra que las colisiones aparecen mucho antes de lo previsto.
Criptografía. Aquí es donde la raíz cuadrada determina el parámetro de seguridad. Para encontrar dos documentos diferentes con el mismo hash de 64 bits no hacen falta 2⁶⁴ intentos; bastan unos 2³² —aproximadamente cuatro mil millones, lo que supone apenas unos minutos de trabajo. Este es el ataque del cumpleaños, y por ello una función hash concebida para ofrecer n bits de resistencia a colisiones debe producir 2n bits de salida. Es la razón por la que se considera que los hashes de 128 bits ofrecen 64 bits de resistencia a colisiones y ya no son aceptables para firmas digitales.
Interpretación de coincidencias. Cualquier conjunto de datos suficientemente grande contiene coincidencias llamativas, y su número escala con las parejas, no con los registros. Que dos personas de un mismo pueblo ganen la lotería, una acumulación de casos de una enfermedad en una calle o dos canciones que suenan parecidas: todo esto se convierte en casi una certeza a gran escala, y tratar cada suceso como algo individualmente improbable constituye el mismo error aritmético que se comete con las personas y los cumpleaños.
La pregunta correcta nunca es "¿cuán improbable es esta coincidencia en particular?", sino "¿cuántas oportunidades había de que se diera alguna coincidencia de este tipo?". Ambas cifras difieren en un factor que crece de forma cuadrática, lo suficiente como para transformar el asombro en algo esperable.
Dos objeciones que conviene responder
"Los cumpleaños no son uniformes." No lo son: hay más nacimientos a finales de verano en el hemisferio norte, menos el 25 de diciembre y el 29 de febrero, y un descenso visible los fines de semana debido a los partos programados. Sin embargo, la falta de uniformidad siempre hace que las coincidencias sean más probables, nunca menos: la aglomeración concentra a las personas en un menor número de días efectivos. Por lo tanto, la hipótesis de uniformidad es conservadora, y 23 es, en todo caso, una estimación ligeramente al alza.
"Gemelos y personas que vienen juntas." Las salas reales no son muestras aleatorias. Una estancia en la que haya hermanos, o una clase de escolares seleccionados por fecha de corte académica, presenta correlaciones que el modelo no contempla. El cálculo constituye una línea base para extracciones independientes, y cuando estas no son independientes, lo que requiere defensa es la independencia, no la aritmética.
La versión para llevar consigo
Si hay N categorías igualmente probables y se realizan k extracciones, el número esperado de parejas que colisionan es de aproximadamente k²/2N. Igualando esa expresión a uno se obtiene k ≈ √(2N): la misma raíz cuadrada, calculada contando las colisiones esperadas en lugar de las probabilidades, y más sencilla de calcular de cabeza.
Para mil posiciones de hash: √2000 ≈ 45, por lo que cabe esperar la primera colisión en torno a los cuarenta. Para una suma de comprobación de 32 bits: 2¹⁶ = 65.536 elementos, cifra que un archivo de registro alcanza en una tarde. Para 365 días: 27, lo bastante cerca de 23 como para confiar en la estimación.
El hábito consiste en recurrir a la raíz cuadrada cada vez que surge la pregunta "¿cuál es la probabilidad de un duplicado?", y observar que la respuesta llega mucho antes de lo que sugiere el tamaño del espacio. La herramienta Birthday Paradox representa gráficamente la curva, y su pronunciada pendiente en torno a las 20 a 30 personas es la parte que resulta imposible transmitir solo con palabras.