De paradojas, cumpleaños y perfiles genéticos

¿Cúantas personas debe tener un grupo para que haya un 50% de probabilidades de que al menos dos miembros del mismo cumplan años el mismo día?

Así queda enunciada la denominada "paradoja del cumpleaños", un resultado matemático que resulta paradójico no por desafiar ninguna verdad matemática sino por contradecir la intuición. Mucha gente piensa que el grupo debe tener al menos cien miembros cuando en realidad la probabilidad que de que en un grupo de cien personas al menos dos cumplan años el mismo día es altísima, exactamente del 0.9999997. Lo cierto es que para que las posibilidades sean del 50% basta con que el grupo tenga 23 personas.

Esto se debe a que, aunque la probabilidad de que un persona concreta encuentre otra con la misma fecha de nacimiento es realmente pequeña, la probabilidad de que haya un par cualquiera de miembros del grupo nacidos el mismo día del año es mucho mayor, ya que el número de parejas que se pueden crear crece exponencialmente con el tamaño del grupo. Concretamente, se puede emparejar a 23 personas de 253 formas distintas, y de un grupo de 100 personas podemos sacar 4950 parejas diferentes. Aunque para cada pareja la probabilidad de cumplir años el mismo día es baja, hay tantas parejas para probar que la probabilidad de que haya una "colisión" crece muy rápido.

Hasta aquí podríamos tener una curiosidad matemática, ni siquiera una paradoja sino más bien una anécdota que ilustraría hasta que punto los resultados de la teoría de probabilidades contradicen la intuición. Sin embargo la criptografía, y mas concretamente las firmas digitales, pueden ser susceptibles del llamado ataque de cumpleaños. Un mensaje m se suele firmar calculando primero el valor f(m), donde f es una función resumen o función hash. El siguiente ejemplo extraido de la Wikipedia ilustra cómo funciona un ataque de cumpleaños en un contexto criptográfico

Supongamos que Alice quiere engañar a Bob para que firme un contrato fraudulento. Alice prepara un contrato bueno m y uno malo m'. Así, ella busca un número de posiciones donde m pueda ser modificado sin cambiar el significado, como por ejemplo insertando comas, líneas en blanco, cambiando el espaciado entre oraciones, usando sinónimos, etc. Combinando estos cambios, Alice podría crear un número inmenso de variaciones de m, todas ellas contratos buenos. De manera similar, podría crear un número inmenso de contratos fraudulentos m'. Entonces, ella aplica una función de hash a todas esas variaciones hasta que encuentre una versión del contrato bueno y otra del malo que posean el mismo valor hash, f(m) = f(m'). Luego, le presenta la versión buena a Bob para que la firme. Una vez que Bob la firma, Alice toma la firma y se la adjunta al contrato frudulento. La firma digital "prueba" entonces que Bob firmó el contrato fraudulento

Esta es la razón por la que las funciones hash usadas en criptografía usan longitudes de bit superiores a 128. 2 elevado a 128 es un número enorme, mayor que el número de mensajes diferentes que se puede esperar que sea jamás intercambiado. Sin embargo se hace necesario usar longitudes de hash superiores debido a la "paradoja del cumpleaños". De hecho, una de las funciones clásicas de hashing criptográfico, MD5, "cayó" ya hace varios años y no se considera suficientemente segura.

Venga, un poquito más y ya termino :-) Según la Wikipedia la huella genética, también llamada pruebas de ADN o análisis de ADN

es una técnica utilizada para distinguir entre los individuos de una misma especie utilizando muestras de su ADN. Para distinguir a dos individuos se puede explotar la repetición de secuencias altamente variables llamada microsatélites. Dos seres humanos no relacionados será poco probable que tengan el mismo número de microsatélites en un determinado locus. La reacción en cadena de polimerasa (PCR) se utiliza para obtener suficiente ADN para luego detectar el número de repeticiones en varios loci (posiciones fijas sobre un cromosoma, como la posición de un gen o de un marcador genético)

Cuando se encuentra un rastro genético (sangre, cabellos, piel) y el perfil encaja con el de un sospechoso, esto suele sellar su suerte incluso en ausencia de otra evidencia. Mientras que se cuestionan los resultados de balística, pruebas dentales e incluso dactilares, la huella genética es oro puro y se muestra como algo irrefutable. Pero los perfiles no son lo que parecen, y aunque el genoma de cada persona es único, su perfil genético es el resultado de un muestreo, un hash... Ummmm, esto me suena...

La siguiente historia apareció en Los Angeles Times el pasado mes de Julio: en 2001 la genetista Kathryn Troyer estaba trabajando en una base de datos de ADN cuando encontró dos perfiles genéticos sorprendentemente similares. Los perfiles genéticos de los dos presos coincidían en 9 de 13 loci, pero uno de los convictos era blanco y el otro negro... Algo no encajaba. Los cálculos del FBI estiman que la probabilidad de que dos personas no emparentadas compartan esos marcadores es de 1 entre 13.000.000.000. A partir de eso momento Troyer empezó a buscar coincidencias y encontró que en una base de datos de 65.000 condenados había 102 parejas que coincidían en 9 de 13 loci, y 20 parejas que coincidían en 10 de 13. Cada una de estas parejas desafía probabilidades de forma aparentemente imposible. El FBI, responsable de CODIS, la mayor base de datos de perfiles genéticos, intentó impedir la distribución de estos datos y poner trabas a estudios similares.

Pero, ¿pueden estar los números del FBI en lo cierto, y a la vez haber 122 parejas con 9 o más coincidencias de 13 en la base de datos? Paradójicamente (o, a estas alturas, ¿no sería mejor decir antiintuitivamente?), la respuesta es afirmativa. Si la probabilidad de que dos individuos coincidan en un locus es del 7.5%, la probabilidad de que dos personas al azar coincidan en 13 loci es de 1 en 400 trillones. Si lo dejamos en 9 loci, la probabilidad es de 1 en 13 mil millones.

Paradoja del cumpleaños al rescate ¿Cúantas parejas deberíamos esperar encontrar con una coincidencia de 9 sobre 13 loci en una base de datos de 65.000 entradas? Con 65000 personas nos salen dos mil millones de posibles parejas. Como además no necesitamos que encajen en 9 loci concretos sino que pueden ser cualesquiera 9 de los 13 loci, para cada una de esas parejas tenemos 700 combinaciones a explorar... Podeis ver los números en Freakonomics, pero las cuentas que echan vienen a indicar que en un grupo de 65.000 personas, habrá unas 100 que coincidan en 9 loci... ¿No es asombroso? A algunos abogados de la defensa desde luego ya se lo ha parecido...

Coda:

Python 2.5.1 (r251:54863, Apr 18 2007, 08:51:08) [MSC v.1310 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
IDLE 1.2.1     
>>> from random import randint
>>> grupo=[randint(1,365) for x in range(23)]
>>> grupo
[260, 12, 351, 68, 290, 237, 257, 358, 216, 126, 156, 155, 201, 43, 163, 162, 1, 14, 284, 299, 228, 199, 234]
>>> grupo=[randint(1,365) for x in range(23)]
>>> grupo
[172, 220, 150, 285, 53, 195, 220, 187, 227, 337, 346, 12, 306, 33, 292, 190, 56, 272, 358, 75, 355, 16, 2]
>>> def dups(seq):
 vistos=[]
 encontrados=[]
 for e in seq:
        if e in vistos:
               encontrados.append(e)
        vistos.append(e)
 return encontrados
>>>
>>> dups(grupo)
[220]
>>> contador=0
>>> for i in range(5000):
 grupo=[randint(1,365) for x in range(23)]
 if dups(grupo):
        contador+=1
>>>
>>> print contador/5000.0
0.5026

Fuente: Schneier. ¿Sigues ahí? Venga, vamos, apúntate (feed RSS). Si no sabes qúe es el RSS (o mejor aún, te da igual :-) siempre puedes apuntarte por correo...