Saltar al contenido ForoHackers

La paradoja del cumpleaños, explicada con la cola de la panadería

AlgoritmosMatemática discretaProbabilidad y estadística
#1057 · SiestaDeAlgoritmos · · Denunciar

Pregunta: ¿cuántas personas hacen falta en la cola de la panadería para que sea más probable que no que dos cumplan años el mismo día?

La intuición dice "unas 180" (la mitad de 365). La respuesta correcta es 23.

El truco es contar lo contrario. La probabilidad de que nadie coincida es: la segunda persona tiene 364 días libres de 365, la tercera 363 de 365, y así:

p = 1.0
for k in range(23):
    p *= (365 - k) / 365
print(1 - p)   # 0.5072972...

Con 23 personas hay 253 parejas posibles (23*22/2), y cada pareja es una oportunidad de coincidir. Nuestra intuición cuenta personas; el problema cuenta parejas, y las parejas crecen con el cuadrado.

(Supuesto: los cumpleaños son uniformes e independientes y no hay 29 de febrero. En la realidad no son del todo uniformes, y eso solo sube un poco la probabilidad.)

#1598 · PacoElDelCronjob · · Denunciar

Pole. Y zasca a mi intuición, que en la panadería de mi barrio habría jurado que hacían falta cien personas. Se lo voy a plantear en el bar a ver cuántos aciertan.

#1599 · TochopostDeLosLunes · · Denunciar

Esto es exactamente por lo que las colisiones de hash llegan "antes de lo esperado". Para un hash de b bits, la probabilidad de colisión pasa del 50% cuando tienes del orden de 1,18 * 2^(b/2) elementos. Con 32 bits son unos 77 000 elementos, no cuatro mil millones. Con 64 bits ya hablamos de unos 5 000 millones, que sigue siendo mucho, pero deja de ser "imposible".

Por eso para identificadores que no pueden colisionar se usan 128 bits o más, y por eso conviene no truncar un hash "porque total, es único".

#1600 · TortugaConRoot · · Denunciar

Muy bien explicado. Yo lo había entendido mal siempre porque pensaba "mi cumpleaños contra el de los demás", que es otro problema distinto y sí necesita unas 253 personas. Contar parejas es la clave.

#1601 · LaAbuelaDelCOBOL · · Denunciar

Lo he vivido con identificadores de seis dígitos asignados "al azar". Con un millón de valores posibles, la colisión llega al 50% con unos 1 200 registros, no con 500 000. Ese día aprendimos lo de las parejas, y a mí me tocó la reunión de tres horas.

Inicia sesión o únete para responder.