Présentation

Supposons que je vous demande combien de personnes devraient être dans une pièce pour que deux d'entre elles fêtent leur anniversaire avec une probabilité de 50% d'un jour. Quelle sera la réponse? C'est ce qu'on appelle le paradoxe d'anniversaire.

Le paradoxe se lit comme suit:

S'il y a 23 personnes dans la pièce, alors avec une probabilité de 50%, deux d'entre elles sont nées le même jour.

Certaines versions du paradoxe font des déclarations encore plus fortes:

Si la salle compte 70 personnes, alors avec une probabilité de 99%, deux d'entre elles sont nées le même jour.

Au début, cela m'a paru surprenant et contre-intuitif. Voyons pourquoi cela est vrai. Pour simplifier la tâche, nous faisons les hypothèses suivantes:

1. Nous supposons que toutes les personnes présentes dans la pièce ne sont pas nées au cours d'une année bissextile. Nous faisons cette hypothèse pour ne pas avoir à analyser deux cas différents.
2. Il n'y a pas de jumeaux dans la chambre. Avec une paire de jumeaux, la solution sera triviale.
3. Nous supposons que les gens naissent de façon égale et aléatoire. Qu'est-ce que cela signifie? Les gens sont également susceptibles de naître n'importe quel jour de l'année. Si cela est un peu formalisé, alors la probabilité de naissance un jour choisi est égale à $$$\ frac {1} {365}$ .
4. Les gens naissent indépendamment les uns des autres. Cela signifie que la date de naissance d'une personne n'affecte pas la date de naissance d'une autre.

Il convient de noter que ces conditions ne sont pas nécessairement observées dans le monde réel. En particulier, dans le monde réel, les gens ne naissent pas avec un caractère aléatoire uniforme. Ce lien contient des statistiques sur les jours de naissance des personnes. Bien que notre modèle ne reflète pas fidèlement le monde réel, sa simplicité facilite beaucoup l'analyse du problème.

Je dois dire que s'il y a 366 personnes ou plus dans une pièce, alors il est garanti d'avoir deux personnes avec le même anniversaire. Cela découle du principe Dirichlet (le «principe des pigeons et des boîtes»): s'il y a 366 personnes et 365 jours, alors au moins deux personnes doivent avoir le même anniversaire.

Imaginez qu'il y ait une personne dans la pièce, alors la probabilité de son anniversaire commun avec quelqu'un d'autre est de 0. Soit $$$(A_n)$ sera le résultat dans lequel parmi $$$n$ les gens n'ont pas un seul anniversaire. Soit $$$\ Pr [A_n]$ - la probabilité que parmi $$$n$ de personnes dans la salle, tout le monde fête son anniversaire. De même, laissez $$$\ overline {A_n}$ sera complémentaire $$$A_n$ , c'est-à-dire un résultat dans lequel parmi $$$n$ les gens deux personnes ont le même anniversaire.

$$

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

$$

$$\ Pr [A_1] = 1 \ text {car il n'y a qu'une seule personne dans la pièce}$$

Supposons qu'il y ait deux personnes dans la pièce, A et B. Sans perte de généralisation, imaginez simplement que la personne A est née le 1er janvier. Pour que B et A aient des anniversaires différents, B doit naître n'importe quel jour sauf le 1er janvier. La personne B aura 364 options d'anniversaire.

$$

$$\ Pr [A_2] = \ Pr [\ text {B est différent de A}] = \ frac {364} {365}$$

Imaginez qu'il y ait trois personnes dans la pièce, A, B et C. Supposons que la personne A soit née le 1er janvier, de sorte que toutes soient nées à des jours différents, la personne B n'a eu que 364 jours, comme dans l'exemple précédent. Puisque A et B prennent deux jours, la personne C ne peut naître qu'à 365 - 2 = 363 jours.

$$

$$\ Pr [A_3] = \ Pr [\ text {B est différent A et C est différent de B, A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

Quelque chose de plus intéressant se passe ici: supposons que la pièce a déjà $$$k - 1$ les gens. Quand il entre dans la pièce $$$k$ cette personne $$$k$ les gens avaient des anniversaires différents, deux résultats doivent être vrais

1. Tous $$$k - 1$ les personnes qui sont entrées dans la pièce avant lui devraient avoir des anniversaires différents. Quelle est la probabilité de cela? $$$\ Pr [A_ {k-1}]$ .
2. $$$k$ - cette personne doit avoir un anniversaire différent de tous les autres $$$k - 1$ les gens dans la salle. Quelle est la probabilité de cela? $$$\ frac {365 - (k-1)} {365}$ .

Il convient également de noter que les deux résultats présentés ci-dessus sont indépendants l'un de l'autre, car selon l'hypothèse (4) faite au début du poste, $$$k$ La deuxième personne est née indépendamment de toutes les autres.

$$$$ afficher $$ \ commencer {équation *} \ commencer {scinder} \ Pr [A_k] & = \ Pr [k - 1 \ text {les personnes dans la pièce ont des anniversaires différents} \ textbf {AND} \\ & \ \ \ \ \ \ \ \ text {la personne k a un anniversaire différent du} k - 1 \ text {people}] \\ & = \ Pr [k - 1 \ text {les personnes dans la pièce ont des anniversaires différents}] \\ & \ \ \ \ \ times \ Pr [\ text {la personne k a un anniversaire différent du} k - 1 \ text {people}] \\ & = \ Pr [A_ {k-1}] \ times \ frac { 365 - (k-1)} {365} \ end {split} \ end {equation *} $$ display $$

Maintenant, nous calculons les probabilités:

$$$$ afficher $$ \ begin {équation *} \ begin {split} \ Pr [A_1] & = 1 \\ \ Pr [A_2] & = \ Pr [A_1] \ times \ frac {364} {365} = \ frac {364} {365} \ environ 0,997 \\ \ Pr [A_3] & = \ Pr [A_2] \ times \ frac {363} {365} = \ frac {364} {365} \ times \ frac {363} {365} \ environ 0,991 \\ \ Pr [A_4] & = \ Pr [A_3] \ times \ frac {362} {365} \ environ 0,983 \\ & \ vdots \\ \ Pr [A_ {22}] & = \ Pr [A_ {21}] \ times \ frac {344} {365} \ environ 0,525 \\ \ Pr [A_ {23}] & = \ Pr [A_ {22}] \ times \ frac {343} {365 } \ environ 0,493 \\ \ end {split} \ end {équation *} $$ display $$

Depuis que nous avons $$$\ Pr [A_ {23}] = 0,493 <0,5$ , cela signifie que la probabilité d'un anniversaire commun pour deux personnes est égale

$$

$$\ Pr [\ overline {A_ {23}}] = 1 - \ Pr [A_ {23}] = 1 - 0,493 = 0,507> 0,5$$

Avec augmentation $$$n$ la probabilité tend vers 1 et l'atteint.

Tâche plus difficile

Supposons que nous voulons généraliser ce problème au cas où il y a $$$n$ les gens et $$$m$ anniversaires possibles. Ayant $$$n, m$ , pouvons-nous déterminer la probabilité que deux personnes aient un anniversaire en commun?

Vous pouvez utiliser le même système: nous aurons un résultat $$$A_n$ dénotant tout $$$n$ les personnes nées à des jours différents. Dans le cas d'une seule personne, rien ne change

$$

$$\ Pr [A_1] = 1$$

Dans le cas où il y a deux personnes, nous les désignons comme A et B.Pour que la personne B naisse un autre jour, la personne B doit avoir un anniversaire parmi $$$m - 1$ d'autres options.

$$

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

Dans le cas de trois personnes, la personne B doit avoir un anniversaire différent de l'anniversaire de A. La personne C doit avoir un jour différent des anniversaires de A et B.

$$

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

Généralement pour tout $$$n$ nous pouvons utiliser la même formule récursive que dans la section précédente:

$$

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

Supposons que si nous voulons trouver une expression sous forme fermée pour $$$\ Pr [A_n]$ , puis on décompose l'expression

$$$$ affiche $$ \ begin {equation *} \ 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 {en utilisant l'identité} 1 - x \ approx e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ approx e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {equation *} $$ display $$

Une approximation de ce résultat est $$$\ Pr [A_n] \ environ e ^ {\ frac {-n ^ 2} {2m}}$ . Bien que nous puissions trouver des frontières plus approximatives, cela nous donne une approximation suffisante. La seule identité que nous avons utilisée dans cette approximation:

$$

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

Dans sa forme abstraite, le paradoxe d'anniversaire a de nombreuses utilisations en informatique. En particulier, il est utilisé dans le hachage, qui en soi a de nombreuses utilisations. Les conclusions tirées dans cette tâche sont essentielles pour analyser la probabilité de hacher deux éléments en une seule clé. Ce problème peut être davantage généralisé au problème probabiliste des boules et des bassins (problème des boules et des bacs), que nous laisserons pour un autre article.

Candidature

Le paradoxe d'anniversaire n'est pas seulement une tâche artificielle ou un tour de fête intéressant, il a de nombreuses applications dans le monde réel. Personnellement, je crois que l'analyse probabiliste utilisée dans la preuve est utile pour analyser d'autres tâches dans lesquelles la randomisation est impliquée. En particulier, cela concerne le développement de fonctions de hachage cryptographiques. Nous verrons comment l'analyse faite ci-dessus peut être très utile pour créer des fonctions de hachage avec une protection contre les attaques des «anniversaires».

Tout d'abord, définissons ce qu'est une fonction de hachage. Fonction de hachage $$$h: U \ rightarrow [0, m-1]$ Est une fonction qui effectue un mappage à partir d'un ensemble $$$U$ en nombre dans la gamme $$$[0, m-1]$ . Fonction $$$h$ défini comme $$$h (x) = x \ mod m$ - exemple de fonction de hachage de $$$\ mathbb {N} \ rightarrow [0, m-1]$ . Les fonctions de hachage ont de nombreuses utilisations, en particulier en combinaison avec la structure de données de table de hachage populaire. Il est également utilisé en cryptographie, où un type spécifique de fonction de hachage appelé «fonction de hachage cryptoraphique» est utilisé.

L'une des nombreuses propriétés qu'une fonction de hachage cryptoraphique doit avoir est la résistance aux collisions. Il doit être difficile de trouver deux $$$u_1, u_2 \ in U$ de sorte qu'ils forment une collision, c'est-à-dire $$$h (u_1) = h (u_2)$ .

C'est sur la résistance aux collisions que nous allons nous concentrer. Tout d'abord, je vais expliquer pourquoi c'est une propriété souhaitable. Pour ce faire, nous considérerons d'abord les signatures numériques.

Dans le passé, des personnes et des organisations utilisaient des signatures et des sceaux pour «signer» des documents. Récemment, il y a eu une transition vers les signatures électroniques ou numériques. Une signature numérique doit satisfaire trois propriétés de base.

1. Lors de la signature d'un document, vous devez être en mesure de vérifier qui a signé le document.
2. Après avoir signé le document, personne ne devrait pouvoir le simuler.
3. La personne qui a signé le document ne peut par la suite réfuter la signature du document.

Une signature numérique est un moyen de vérifier la véracité d'un document ou d'un message. Une signature numérique garantit que le message reçu a été créé par un expéditeur connu et n'a pas été modifié.

Disons que nous avons un document $$$m$ . Comment le signe-t-on?

Chaque utilisateur / organisation possède une clé privée unique $$$p_k$ et clé publique $$$pub_k$ . Ils utilisent la fonction de signature pour signer un document avec leur propre clé privée. Cependant, une signature numérique ne peut signer qu'un petit nombre de documents. La portée de la fonction de signature est petite. Une façon de résoudre ce problème consiste à créer un document plus petit qui représente le document d'origine, mais dans une taille beaucoup plus petite. Le plus souvent, une fonction de hachage est appliquée à ce document volumineux. Une fonction de hachage est utilisée pour la mapper d'un grand espace à un plus petit, et le résultat d'une telle opération est appelé une «empreinte digitale». La signature utilise l'empreinte digitale et la clé privée pour créer la signature. La procédure peut être décrite comme suit:

1. Obtenez la clé privée $$$p_k$ .
2. Hachage d'un document $$$m$ et obtenez $$$h (m)$ .
3. Signe $$$h (m)$ en utilisant la clé privée $$$p_k$ .
4. Nous envoyons $$$signe (h (m), p_k)$ et clé publique $$$pub_k$ toute personne qui souhaite confirmer le document.

Quiconque a $$$signe (h (m), p_k))$ et la clé publique, peuvent vérifier si le document est vraiment $$$m$ signé par la bonne personne.

Problème: supposons que l'attaquant Eva ait trouvé deux documents $$$m, m '$ où $$$m$ - c'est le présent contrat, et $$$m '$ - un document frauduleux tel que $$$h (m) = h (m ')$ . Supposons qu'Ève sache à l'avance qu'Alice ne signera que $$$m$ mais pas $$$m '$ . Avant de signer, une fonction de hachage cryptographique est appliquée au document $$$h$ . Eve va voir Alice et lui demande de signer un document $$$m$ en utilisant la séquence décrite ci-dessus. Maintenant, Eve peut prétendre qu'Alice a signé un document frauduleux $$$m '$ parce que $$$h (m) = h (m ')$ . Alice ne pourra prouver d'aucune façon qu'elle n'a pas signé $$$m '$ .

Dans l'exemple ci-dessus $$$h$ s'est avéré être une fonction anti-collision, donc Eve a pu trouver deux ensembles de données entrants qui hachaient la même valeur. Eve a pu prétendre qu'Alice avait signé $$$m '$ bien qu'en fait, elle a signé seulement $$$m$ . Cela souligne l'importance de la résistance aux collisions et montre pourquoi les signatures numériques sont vulnérables si la fonction de hachage est instable.

Soit $$$h: U \ rightarrow [0, m-1]$ sera une fonction de hachage. Supposons que les données d'entrée soient hachées de manière aléatoire et uniforme dans l'un des éléments $$$m$ .

La tâche de l'attaque «anniversaire» est de trouver le plus petit nombre d'éléments $$$n$ qui peut être haché avec $$$h$ afin que nous puissions trouver deux éléments $$$x, y \ in U$ à quel $$$h (x) = h (y)$ .

Lorsqu'il attaque des «anniversaires», l'attaquant ramasse au hasard $$$x \ in U$ et garder les couples $$$(x, h (x))$ . Un attaquant sélectionnera et sauvegardera ces paires à plusieurs reprises jusqu'à ce qu'il trouve deux valeurs $$$x, y$ à quel $$$h (x) = h (y)$ . Nous devons déterminer combien de fois l'attaquant doit répéter cette opération jusqu'à ce qu'il trouve une collision.

Pour analyser l'attaque des «anniversaires», vous pouvez utiliser les mêmes principes que nous avons utilisés pour le paradoxe d'anniversaire. Dans l'attaque des "anniversaires" $$$m$ indique le nombre de jours dans une année, et $$$U$ semblable aux personnes entrant dans une pièce. Les gens sont hachés le jour de leur anniversaire, ce qui peut être l'une des significations. $$$m$ . Disons que nous devons trouver une collision avec une probabilité de 99%. Nous devons savoir quel est le plus petit $$$n$ , dans lequel le hachage de deux valeurs sera un anniversaire (dans le monde des fonctions de hachage, cela signifie que deux ensembles de données d'entrée sont hachés dans la même valeur).

Nous avons montré précédemment que $$$\ Pr [A_n] \ environ e ^ {\ frac {-n ^ 2} {2m}}$

Nous voulons demander $$$\ Pr [\ overline {A} _n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ c'est $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ .

$$$$ afficher $$ \ begin {équation *} \ 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 {equation *} $$ display $$

L'analyse ci-dessus nous indique que pour obtenir des collisions dans les fonctions de hachage avec un intervalle de taille $$$m$ un attaquant doit hacher de manière uniforme et indépendante environ $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ pour une garantie presque complète (probabilité de 99%) que deux éléments sont hachés à la même valeur.

Supposons que nous voulons obtenir une collision avec une probabilité de 50%; alors nous avons besoin $$$n = \ sqrt {2 m \ ln 2}$ . La conclusion importante ici est que pour obtenir une collision avec une probabilité supérieure à 0,5, nous devons hacher l'ordre $$$\ sqrt {m}$ éléments. Ceci est cohérent avec notre analyse précédente pour $$$m = 365$ parce que $$$\ sqrt {2 \ ln 2 \ cdot 365}$ environ égal à 23.

Tâches supplémentaires

1. Ayant $$$n$ de personnes $$$m$ jours et un certain nombre $$$k$ trouver la probabilité qu'exactement $$$k$ les gens ont le même anniversaire.
2. Transformons un peu la tâche ci-dessus. Disons que nous avons $$$m$ jours et un certain nombre $$$k$ . Quelle sera la plus petite valeur $$$n$ où pas moins $$$k$ les gens auront le même anniversaire avec une probabilité d'au moins 0,5? Pouvez-vous généraliser cette tâche à n'importe quelle probabilité $$$p> 0$ ?
3. Supposons que nous ayons 100 nombres de 1 à 100, ainsi qu'une machine devinant un nombre aléatoire de 1 à 100 dans un ordre uniforme et aléatoire. Combien de fois aurons-nous besoin d'utiliser la machine comme prévu, pour que la machine devine tous les nombres de 1 à 100?
4. Pouvez-vous généraliser cette tâche à tout $$$n$ ?
5. Supposons que nous ayons une fonction de hachage qui affiche de manière uniforme et aléatoire des éléments dans une région de mémoire. Soit des surfaces totales $$$m$ . Combien d'articles $$$n$ devons-nous ajouter une attente mathématique à notre structure de données afin qu'au moins deux éléments soient hachés dans chaque région?