		*Últimos Cambios*
	Blog personal: El hilo del laberinto

La paradoja del cumpleaños

Última Actualización: 18 de Marzo de 2003 - Martes

¿Cuántas personas necesitamos reunir, de forma aleatoria, para que dos de ellas tengan su cumpleaños el mismo día con una probabilidad mayor del 50%?. La cifra es sorprendentemente baja: basta con 23 personas.

Intuitivamente parecería que necesitamos muchas más personas, de ahí que se denomine "la paradoja del cumpleaños". Las matemáticas, no obstante, no engañan.

Por simple enumeración, es fácil deducir que la probabilidad de que dos "eventos" coincidan entre un número dado de posibilidades es de:

                  d!
P2(n,d) = 1 - ----------
               (d-n)!dⁿ

donde n es el número de eventos en el sistema, y d es el número de posibilidades diferentes.

En el caso de los cumpleaños, y tomando 23 y 365 como parámetros (ignoramos los años bisiestos y suponemos que todos los cumpleaños son equiprobables), obtenemos que p2(23,365) = 0.50729723432398544. Es decir, una probabilidad algo mayor del 50%.

Calcular estas probabilidades para valores grandes es muy problemático porque los factoriales crecen a gran velocidad. No obstante esa probabilidad se puede aproximar por

P2'(n,d) = 1 - e^-n(n-1)/2d = 1 - (1-n/2d)^n-1 (con un error máximo de n³/6(d-n+1)²)

Supongamos que queremos calcular la probabilidad p=Pk(n,d) de que existan k coincidencias. La fórmula resultante es bastante compleja, pero se puede aproximar de forma bastante razonable como la resolución de la siguiente ecuación:

ne^-n/(dk) = (d^k-1k!ln(1/(1-p))*(1-n/(d(k+1))))^1/k

Para una probabilidad del 50% y 365 días, el número de personas necesarias para k=1, 2, 3... es de 1, 23, 88, 187, 313, 459, 622, 797, 983, 1179, 1382, 1592, 1809...

Tomando la fórmula aproximada de P2'(n,d), resolviendo para la probabilidad del 50% y suponiendo que n es un número grande, obtenemos la siguiente fórmula simplificada:

n = 1.17741 * sqrt(d)

Ésta es la fórmula simplificada habitual de la paradoja del cumpleaños.

Aplicaciones prácticas

La paradoja del cumpleaños tiene aplicaciones prácticas en el campo de la criptografía y la estadística. Nos indica, por ejemplo que para generar colisiones en una función aleatoria perfecta (en particular, funciones hash) de n bits, con una probabilidad del 50% aproximadamente, se requieren solo 2^n/2 intentos.

Historia

18/Mar/03: Primera versión de este documento.

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS