Introduccion

Supongamos que le pregunto cuántas personas deberían estar en una habitación para que dos de ellos cumplan años con una probabilidad del 50% de un día. ¿Cuál será la respuesta? Esto es lo que se llama la paradoja del cumpleaños.

La paradoja dice:

Si hay 23 personas en la sala, con una probabilidad del 50%, dos de ellas nacieron el mismo día.

Algunas versiones de la paradoja hacen declaraciones aún más fuertes:

Si la sala tiene 70 personas, entonces con una probabilidad del 99%, dos de ellas nacieron el mismo día.

Al principio, esto me pareció sorprendente y contradictorio. Veamos por qué esto es cierto. Para simplificar la tarea, hacemos los siguientes supuestos:

1. Suponemos que todas las personas en la sala no nacieron en un año bisiesto. Hacemos esta suposición para no tener que analizar dos casos diferentes.
2. No hay gemelos en la habitación. Con un par de gemelos, la solución será trivial.
3. Asumimos que las personas nacen de manera uniforme y aleatoria. ¿Qué significa esto? Es igualmente probable que las personas nazcan cualquier día del año. Si esto se formaliza un poco, entonces la probabilidad de nacimiento en cualquier día elegido es igual a $$$\ frac {1} {365}$ .
4. Las personas nacen independientemente unas de otras. Esto significa que la fecha de nacimiento de cualquier persona no afecta la fecha de nacimiento de otra.

Vale la pena señalar que estas condiciones no se observan necesariamente en el mundo real. En particular, en el mundo real, las personas no nacen con aleatoriedad uniforme. Este enlace tiene estadísticas de los días en que nacen las personas. Aunque nuestro modelo no es un reflejo preciso del mundo real, su simplicidad hace que sea mucho más fácil analizar el problema.

Debo decir que si hay 366 o más personas en una habitación, entonces se garantiza que habrá dos personas con el mismo cumpleaños. Esto se desprende del principio de Dirichlet (el "principio de palomas y cajas"): si hay 366 personas y 365 días, entonces al menos dos personas deben tener el mismo cumpleaños.

Imagina que hay una persona en la habitación, entonces la probabilidad de su cumpleaños común con otra persona es 0. Deja $$$(A_n)$ será el resultado en el cual entre $$$n$ La gente no tiene un solo cumpleaños. Dejar $$$\ Pr [A_n]$ - la probabilidad de que entre $$$n$ de las personas en la sala, todos cumplen años en su día. Del mismo modo, dejemos $$$\ overline {A_n}$ será complemento $$$A_n$ es decir un resultado en el que entre $$$n$ personas dos personas tienen el mismo cumpleaños.

$$

$$\ Pr [A_n] + \ Pr [\ overline {A_n}] = 1$$

$$

$$\ Pr [A_1] = 1 \ text {porque solo hay una persona en la habitación}$$

Supongamos que hay dos personas en la sala, A y B. Sin pérdida de generalización, imagínense que la persona A nació el 1 de enero. Para que B y A tengan cumpleaños diferentes, B debe nacer en cualquier día, excepto el 1 de enero. La persona B tendrá 364 opciones de cumpleaños.

$$

$$\ Pr [A_2] = \ Pr [\ text {B es diferente de A}] = \ frac {364} {365}$$

Imagine que hay tres personas en la sala, A, B y C. Suponga que la persona A nació el 1 de enero, de modo que todas nacieron en días diferentes, la persona B solo tuvo 364 días, como en el ejemplo anterior. Como A y B toman dos días, la persona C solo puede nacer a los 365 - 2 = 363 días.

$$

$$\ Pr [A_3] = \ Pr [\ text {B es diferente A y C es diferente de B, A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

Aquí sucede algo más interesante: supongamos que la habitación ya tiene $$$k - 1$ personas Cuando entra en la habitación $$$k$ esa persona $$$k$ las personas tuvieron cumpleaños diferentes, dos resultados deben ser ciertos

1. Todos $$$k - 1$ las personas que entraron a la habitación antes que él deberían tener cumpleaños diferentes. ¿Cuál es la probabilidad de esto? $$$\ Pr [A_ {k-1}]$ .
2. $$$k$ - esa persona necesita tener un cumpleaños diferente al resto $$$k - 1$ gente en la sala ¿Cuál es la probabilidad de esto? $$$\ frac {365 - (k-1)} {365}$ .

También se debe tener en cuenta que los dos resultados presentados anteriormente son independientes entre sí, porque por el supuesto (4) hecho al comienzo de la publicación, $$$k$ La segunda persona nació independientemente de todas las demás.

$$$$ display $$ \ begin {ecation *} \ begin {split} \ Pr [A_k] & = \ Pr [k - 1 \ text {las personas en la habitación tienen cumpleaños diferentes} \ textbf {AND} \\ & \ \ \ \ \ \ \ \ text {la persona k tiene un cumpleaños diferente del} k - 1 \ text {people}] \\ & = \ Pr [k - 1 \ text {las personas en la habitación tienen cumpleaños diferentes}] \\ & \ \ \ \ \ times \ Pr [\ text {persona k tiene un cumpleaños diferente del} k - 1 \ text {people}] \\ & = \ Pr [A_ {k-1}] \ times \ frac { 365 - (k-1)} {365} \ end {split} \ end {ecuación *} $$ display $$

Ahora calculamos las probabilidades:

$$$$ display $$ \ begin {ecation *} \ begin {split} \ Pr [A_1] & = 1 \\ \ Pr [A_2] & = \ Pr [A_1] \ times \ frac {364} {365} = \ frac {364} {365} \ aprox. 0.997 \\ \ Pr [A_3] & = \ Pr [A_2] \ times \ frac {363} {365} = \ frac {364} {365} \ times \ frac {363} {365} \ aprox. 0.991 \\ \ Pr [A_4] & = \ Pr [A_3] \ times \ frac {362} {365} \ aprox. 0.983 \\ & \ vdots \\ \ Pr [A_ {22}] & = \ Pr [A_ {21}] \ times \ frac {344} {365} \ aprox 0.525 \\ \ Pr [A_ {23}] & = \ Pr [A_ {22}] \ times \ frac {343} {365 } \ aproximadamente 0.493 \\ \ end {split} \ end {ecuación *} $$ display $$

Desde que tenemos $$$\ Pr [A_ {23}] = 0.493 <0.5$ , esto significará que la probabilidad de un cumpleaños común para dos personas es igual

$$

$$\ Pr [\ overline {A_ {23}}] = 1 - \ Pr [A_ {23}] = 1 - 0.493 = 0.507> 0.5$$

Con aumento $$$n$ la probabilidad tiende a 1 y la alcanza.

Tarea más difícil

Supongamos que queremos generalizar este problema al caso cuando hay $$$n$ personas y $$$m$ posibles cumpleaños Teniendo $$$n, m$ , ¿podemos determinar la probabilidad de que dos personas tengan un cumpleaños común?

Puedes usar el mismo sistema: tendremos un resultado $$$A_n$ denotando todo $$$n$ personas nacidas en días diferentes. En el caso de una persona, nada cambia

$$

$$\ Pr [A_1] = 1$$

En el caso de que haya dos personas, las designamos como A y B. Para que la persona B nazca otro día, la persona B debe cumplir años. $$$m - 1$ Otras opciones.

$$

$$\ Pr [A_2] = \ frac {m-1} {m}$$

En el caso de tres personas, la persona B debe tener un cumpleaños diferente del cumpleaños de A. La persona C debe tener un día diferente de los cumpleaños de A y B.

$$

$$\ Pr [A_3] = \ frac {m-1} {m} \ times \ frac {m-2} {m}$$

Generalmente para cualquier $$$n$ Podemos usar la misma fórmula recursiva que en la sección anterior:

$$

$$\ Pr [A_n] = \ Pr [A_ {n-1}] \ times \ frac {m - (n-1)} {m}$$

Supongamos que si queremos encontrar una expresión en forma cerrada para $$$\ Pr [A_n]$ , luego descomponemos la expresión

$$$$ display $$ \ begin {ecation *} \ begin {split} \ Pr [A_n] & = \ Pr [A_ {n-1}] \ times \ frac {m - (n-1)} {m} \ \ & = \ Pr [A_ {n-2}] \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ Pr [A_ {n-3}] \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n -1)} {m} \\ & \ \ vdots \\ & = \ Pr [A_2] \ times \ frac {m-2} {m} \ times \ frac {m-3} {m} \ times \ cdots \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ prod_ {i = 1} ^ {n-1} \ frac {mi} {m} = \ prod_ {i = 1} ^ {n-1} 1 - \ frac {i} {m} \\ & \ approx \ prod_ {i = 1} ^ {n-1} e ^ {\ frac {-i} {m}} \ text {usando la identidad} 1 - x \ approx e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ aprox e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {ecuación *} $$ display $$

Una aproximación de este resultado es $$$\ Pr [A_n] \ aprox e ^ {\ frac {-n ^ 2} {2m}}$ . Aunque podemos encontrar límites más aproximados, esto nos da una aproximación suficiente. La única identidad que usamos en esta aproximación:

$$

$$1 - x \ aprox e ^ {- x}$$

En su forma abstracta, la paradoja del cumpleaños tiene muchos usos en la informática informática. En particular, se usa en hashing, que en sí mismo tiene muchos usos. Las conclusiones hechas en esta tarea son clave para analizar la probabilidad de mezclar dos elementos en una clave. Este problema puede generalizarse aún más al problema probabilístico de bolas y cuencas (problema de bolas y papeleras), que dejaremos para otra publicación.

Solicitud

La paradoja del cumpleaños no es solo una tarea artificial o un truco de fiesta interesante, tiene muchas aplicaciones del mundo real. Personalmente, creo que el análisis probabilístico utilizado en la evidencia es útil para analizar otras tareas en las que está involucrada la aleatorización. En particular, esto se relaciona con el desarrollo de funciones hash criptográficas. Veremos cómo el análisis realizado anteriormente puede ser bastante útil para crear funciones hash con protección contra ataques de "cumpleaños".

Primero, definamos qué es una función hash. Función hash $$$h: U \ rightarrow [0, m-1]$ Es una función que realiza un mapeo de un conjunto $$$U$ en un número en el rango $$$[0, m-1]$ . Función $$$h$ definido como $$$h (x) = x \ mod m$ - ejemplo de función hash de $$$\ mathbb {N} \ rightarrow [0, m-1]$ . Las funciones hash tienen muchos usos, especialmente en combinación con la popular estructura de datos de la tabla hash. También se usa en criptografía, donde se usa un tipo específico de función hash llamada "función hash criptográfica".

Una de las muchas propiedades que debe tener una función hash criptográfica es la resistencia a la colisión. Debe ser difícil encontrar dos $$$u_1, u_2 \ en U$ para que formen una colisión, es decir $$$h (u_1) = h (u_2)$ .

Nos centraremos en la resistencia a las colisiones. Primero, explicaré por qué es una propiedad deseable. Para hacer esto, primero consideraremos las firmas digitales.

En el pasado, las personas y organizaciones usaban firmas y sellos para "firmar" documentos. Recientemente, ha habido una transición a las firmas electrónicas o digitales. Una firma digital debe satisfacer tres propiedades básicas.

1. Al firmar un documento, debe poder verificar quién firmó el documento.
2. Después de firmar el documento, nadie debería poder falsificarlo.
3. La persona que ha firmado el documento no puede refutar posteriormente la firma del documento.

Una firma digital es una forma de verificar la verdad de un documento o mensaje. Una firma digital asegura que el mensaje recibido fue creado por un remitente conocido y no se modificó.

Digamos que tenemos un documento $$$m$ . ¿Cómo lo firmamos?

Cada usuario / organización tiene una clave privada única $$$p_k$ y clave pública $$$pub_k$ . Usan la función de firma para firmar un documento con su propia clave privada. Sin embargo, una firma digital solo puede firmar una pequeña cantidad de documentos. El alcance de la función de firma es pequeño. Una forma de resolver este problema es crear un documento más pequeño que represente el documento original, pero en un tamaño mucho más pequeño. Muy a menudo, se aplica una función hash a este documento grande. Se utiliza una función hash para asignarlo de un espacio grande a uno más pequeño, y el resultado de dicha operación se denomina "huella digital". La firma utiliza la huella digital y la clave privada para crear la firma. El procedimiento se puede describir de la siguiente manera:

1. Obtenga la clave privada $$$p_k$ .
2. Hash un documento $$$m$ y obtener $$$h (m)$ .
3. Letrero $$$h (m)$ usando la clave privada $$$p_k$ .
4. Enviamos $$$signo (h (m), p_k)$ y clave pública $$$pub_k$ cualquiera que quiera confirmar el documento.

Cualquiera que tenga $$$signo (h (m), p_k))$ y clave pública, puede verificar si el documento es realmente $$$m$ firmado por la persona adecuada.

Problema: supongamos que el atacante Eva encontró dos documentos $$$m, m '$ donde $$$m$ - este es el presente contrato, y $$$m '$ - un documento fraudulento tal que $$$h (m) = h (m ')$ . Supongamos que Eve sabe de antemano que Alice solo firmará $$$m$ pero no $$$m '$ . Antes de firmar, se aplica una función hash criptográfica al documento $$$h$ . Eve va hacia Alice y le pide que firme un documento. $$$m$ usando la secuencia descrita anteriormente. Ahora, Eve puede afirmar que Alice firmó un documento fraudulento $$$m '$ porque $$$h (m) = h (m ')$ . Alice no podrá demostrar de ninguna manera que no firmó $$$m '$ .

En el ejemplo anterior $$$h$ resultó ser una función resistente a colisiones, por lo que Eve pudo encontrar dos conjuntos de datos entrantes que tenían el mismo valor. Eve pudo afirmar que Alice firmó $$$m '$ aunque de hecho ella solo firmó $$$m$ . Esto subraya la importancia de la resistencia a colisiones y muestra por qué las firmas digitales son vulnerables si la función hash es inestable.

Dejar $$$h: U \ rightarrow [0, m-1]$ será una función hash. Suponga que los datos de entrada se combinan aleatoriamente de manera uniforme e independiente en cualquiera de los elementos $$$m$ .

La tarea del ataque de "cumpleaños" es encontrar la menor cantidad de elementos $$$n$ que se puede mezclar con $$$h$ para que podamos encontrar dos elementos $$$x, y \ en U$ en que $$$h (x) = h (y)$ .

Al atacar "cumpleaños", el atacante recogerá al azar $$$x \ en U$ y mantener parejas $$$(x, h (x))$ . Un atacante seleccionará y guardará repetidamente estos pares hasta que encuentre dos valores $$$x, y$ en que $$$h (x) = h (y)$ . Necesitamos determinar cuántas veces el atacante necesita repetir esta operación hasta que encuentre una colisión.

Para analizar el ataque de "cumpleaños", puede usar los mismos principios que usamos para la paradoja del cumpleaños. En el ataque "cumpleaños" $$$m$ denota la cantidad de días en un año, y $$$U$ similar a las personas que ingresan a una habitación. Las personas se divierten en sus cumpleaños, lo que puede ser uno de los significados. $$$m$ . Digamos que necesitamos encontrar una colisión con una probabilidad del 99%. Necesitamos saber cuál es el más pequeño. $$$n$ , en el que el hash de dos valores será un cumpleaños (en el mundo de las funciones hash, esto significa que dos conjuntos de datos de entrada se combinan en el mismo valor).

Anteriormente mostramos que $$$\ Pr [A_n] \ aprox e ^ {\ frac {-n ^ 2} {2m}}$

Queremos preguntar $$$\ Pr [\ overline {A} _n] \ aprox e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ eso es $$$\ Pr [A_n] \ aprox e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ .

$$$$ display $$ \ begin {ecation *} \ begin {split} e ^ {\ frac {-n ^ 2} {2m}} & = \ frac {1} {100} \\ \ frac {n ^ 2} {2m} & = \ ln 100 \\ n ^ 2 & = 2 m \ ln 100 \\ n & = \ sqrt {2 m \ ln 100} \ end {split} \ end {ecuación *} $$ display $$

El análisis que se muestra arriba nos dice que para obtener colisiones en funciones hash con un intervalo de tamaño $$$m$ un atacante debe hacer hash de manera uniforme e independiente aproximadamente $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ para una garantía casi completa (99% de probabilidad) de que dos elementos se combinen con el mismo valor.

Supongamos que queremos obtener una colisión con una probabilidad del 50%; entonces necesitamos $$$n = \ sqrt {2 m \ ln 2}$ . La conclusión importante aquí es que para obtener una colisión con una probabilidad de más de 0.5, tenemos que modificar el orden. $$$\ sqrt {m}$ elementos Esto es consistente con nuestro análisis previo para $$$m = 365$ porque $$$\ sqrt {2 \ ln 2 \ cdot 365}$ aproximadamente igual a 23.

Tareas Adicionales

1. Teniendo $$$n$ de personas $$$m$ días y un cierto número $$$k$ encontrar la probabilidad de que exactamente $$$k$ La gente tiene el mismo cumpleaños.
2. Transformemos un poco la tarea anterior. Digamos que tenemos $$$m$ días y un cierto número $$$k$ . ¿Cuál será el valor más pequeño? $$$n$ en el que no menos $$$k$ las personas tendrán el mismo cumpleaños con una probabilidad de al menos 0.5? ¿Puedes generalizar esta tarea a cualquier probabilidad? $$$p> 0$ ?
3. Supongamos que tenemos 100 números del 1 al 100, así como una máquina que adivina un número aleatorio del 1 al 100 en un orden uniforme y aleatorio. ¿Cuántas veces necesitaremos usar la máquina como se espera, para que la máquina adivine todos los números del 1 al 100?
4. ¿Puedes generalizar esta tarea a cualquier $$$n$ ?
5. Supongamos que tenemos una función hash que muestra elementos aleatoriamente de manera uniforme en una región de memoria. Dejar áreas totales $$$m$ . Cuantos elementos $$$n$ ¿Necesitamos agregar expectativas matemáticas a nuestra estructura de datos para que al menos dos elementos se mezclen en cada región?