Einführung

Angenommen, ich frage Sie, wie viele Personen sich in einem Raum befinden sollen, damit zwei von ihnen mit einer Wahrscheinlichkeit von 50% eines Tages Geburtstag haben. Was wird die Antwort sein? Dies nennt man das Geburtstagsparadoxon.

Das Paradoxon lautet:

Befinden sich 23 Personen im Raum, wurden mit einer Wahrscheinlichkeit von 50% zwei von ihnen am selben Tag geboren.

Einige Versionen des Paradoxons machen noch stärkere Aussagen:

Wenn der Raum 70 Personen hat, wurden mit einer Wahrscheinlichkeit von 99% zwei von ihnen am selben Tag geboren.

Anfangs schien mir das überraschend und nicht intuitiv zu sein. Lassen Sie uns herausfinden, warum dies wahr ist. Um die Aufgabe zu vereinfachen, gehen wir von folgenden Annahmen aus:

1. Wir gehen davon aus, dass nicht alle Personen im Raum in einem Schaltjahr geboren wurden. Wir gehen davon aus, dass wir nicht zwei verschiedene Fälle analysieren müssen.
2. Es sind keine Zwillinge im Raum. Mit einem Paar Zwillinge ist die Lösung trivial.
3. Wir gehen davon aus, dass Menschen gleichmäßig und zufällig geboren werden. Was bedeutet das? Menschen werden mit gleicher Wahrscheinlichkeit an jedem Tag des Jahres geboren. Wenn dies ein wenig formalisiert wird, ist die Wahrscheinlichkeit einer Geburt an einem ausgewählten Tag gleich $$$\ frac {1} {365}$ .
4. Menschen werden unabhängig voneinander geboren. Dies bedeutet, dass das Geburtsdatum einer Person das Geburtsdatum einer anderen Person nicht beeinflusst.

Es ist erwähnenswert, dass diese Bedingungen in der realen Welt nicht unbedingt eingehalten werden. Insbesondere in der realen Welt werden Menschen nicht mit einheitlicher Zufälligkeit geboren. Dieser Link enthält Statistiken für die Tage, an denen Menschen geboren werden. Obwohl unser Modell die reale Welt nicht genau widerspiegelt, erleichtert seine Einfachheit die Analyse des Problems erheblich.

Ich muss sagen, wenn sich 366 oder mehr Personen in einem Raum befinden, sind garantiert zwei Personen mit demselben Geburtstag anwesend. Dies folgt aus dem Dirichlet-Prinzip (dem „Prinzip der Tauben und Kisten“): Wenn es 366 Personen und 365 Tage gibt, müssen mindestens zwei Personen denselben Geburtstag haben.

Stellen Sie sich vor, es befindet sich eine Person im Raum, und die Wahrscheinlichkeit, dass er gemeinsam mit einer anderen Person Geburtstag hat, beträgt 0. Lassen Sie $$$(A_n)$ wird das Ergebnis sein, in dem unter $$$n$ Menschen haben keinen einzigen Geburtstag. Lass $$$\ Pr [A_n]$ - die Wahrscheinlichkeit, dass unter $$$n$ Von den Menschen im Raum hat jeder an seinem Tag Geburtstag. Ebenso lassen $$$\ overline {A_n}$ wird ergänzt $$$A_n$ d.h. ein Ergebnis, in dem unter $$$n$ Menschen zwei Menschen haben den gleichen Geburtstag.

$$

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

$$

$$\ Pr [A_1] = 1 \ text {weil sich nur eine Person im Raum befindet}$$

Angenommen, es befinden sich zwei Personen im Raum, A und B. Stellen Sie sich ohne Verlust der Verallgemeinerung vor, dass Person A am 1. Januar geboren wurde. Damit B und A unterschiedliche Geburtstage haben, muss B an jedem Tag außer dem 1. Januar geboren werden. Person B hat 364 Geburtstagsoptionen.

$$

$$\ Pr [A_2] = \ Pr [\ text {B unterscheidet sich von A}] = \ frac {364} {365}$$

Stellen Sie sich vor, es befinden sich drei Personen im Raum, A, B und C. Angenommen, Person A wurde am 1. Januar geboren, sodass alle an verschiedenen Tagen geboren wurden. Person B hatte nur 364 Tage, wie im vorherigen Beispiel. Da A und B zwei Tage dauern, kann Person C nur mit 365 - 2 = 363 Tagen geboren werden.

$$

$$\ Pr [A_3] = \ Pr [\ text {B ist anders A und C ist anders als B, A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

Hier passiert etwas Interessanteres: Angenommen, der Raum hat bereits $$$k - 1$ Menschen. Wenn er den Raum betritt $$$k$ diese Person $$$k$ Menschen hatten unterschiedliche Geburtstage, zwei Ergebnisse müssen wahr sein

1. Alle $$$k - 1$ Personen, die den Raum vor ihm betreten haben, sollten unterschiedliche Geburtstage haben. Wie hoch ist die Wahrscheinlichkeit dafür? $$$\ Pr [A_ {k-1}]$ .
2. $$$k$ - Diese Person muss einen anderen Geburtstag haben als alle anderen $$$k - 1$ Leute im Raum. Wie hoch ist die Wahrscheinlichkeit dafür? $$$\ frac {365 - (k-1)} {365}$ .

Es sollte auch beachtet werden, dass die beiden oben dargestellten Ergebnisse unabhängig voneinander sind, da nach der Annahme (4), die zu Beginn des Beitrags getroffen wurde, $$$k$ Die zweite Person wurde unabhängig von allen anderen geboren.

$$$$ Anzeige $$ \ begin {Gleichung *} \ begin {split} \ Pr [A_k] & = \ Pr [k - 1 \ text {Personen im Raum haben unterschiedliche Geburtstage} \ textbf {AND} \\ & \ \ \ \ \ \ \ \ text {person k hat einen anderen Geburtstag als} k - 1 \ text {people}] \\ & = \ Pr [k - 1 \ text {Personen im Raum haben unterschiedliche Geburtstage}] \\ & \ \ \ \ \ times \ Pr [\ text {person k hat einen anderen Geburtstag als} k - 1 \ text {people}] \\ & = \ Pr [A_ {k-1}] \ times \ frac { 365 - (k-1)} {365} \ end {split} \ end {Gleichung *} $$ display $$

Nun berechnen wir die Wahrscheinlichkeiten:

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

Da haben wir bekommen $$$\ Pr [A_ {23}] = 0,493 <0,5$ Dies bedeutet, dass die Wahrscheinlichkeit eines gemeinsamen Geburtstages für zwei Personen gleich ist

$$

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

Mit zunehmender Zunahme $$$n$ Wahrscheinlichkeit tendiert zu 1 und erreicht es.

Schwierigere Aufgabe

Angenommen, wir möchten dieses Problem auf den Fall verallgemeinern, wenn es einen gibt $$$n$ Menschen und $$$m$ mögliche Geburtstage. Haben $$$n, m$ Können wir die Wahrscheinlichkeit bestimmen, dass zwei Personen einen gemeinsamen Geburtstag haben?

Sie können das gleiche System verwenden: Wir werden ein Ergebnis haben $$$A_n$ alles bezeichnen $$$n$ Menschen, die an verschiedenen Tagen geboren wurden. Bei einer Person ändert sich nichts

$$

$$\ Pr [A_1] = 1$$

Wenn zwei Personen anwesend sind, bezeichnen wir sie als A und B. Damit Person B an einem anderen Tag geboren wird, muss Person B einen Geburtstag haben $$$m - 1$ andere Optionen.

$$

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

Bei drei Personen muss Person B einen anderen Geburtstag als A haben. Person C muss einen anderen Tag als A und B haben.

$$

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

Generell für jeden $$$n$ Wir können dieselbe rekursive Formel wie im vorherigen Abschnitt verwenden:

$$

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

Angenommen, wir möchten einen Ausdruck in geschlossener Form für finden $$$\ Pr [A_n]$ , dann zerlegen wir den Ausdruck

$$$$ Anzeige $$ \ begin {Gleichung *} \ 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 {unter Verwendung der Identität} 1 - x \ approx e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ ca. e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {Gleichung *} $$ display $$

Eine Annäherung an dieses Ergebnis ist $$$\ Pr [A_n] \ ungefähr e ^ {\ frac {-n ^ 2} {2m}}$ . Obwohl wir ungefährere Grenzen finden können, gibt uns dies eine ausreichende Annäherung. Die einzige Identität, die wir in dieser Annäherung verwendet haben:

$$

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

In seiner abstrakten Form hat das Geburtstagsparadox viele Verwendungsmöglichkeiten im Computercomputer. Insbesondere wird es beim Hashing verwendet, das an sich viele Verwendungszwecke hat. Die in dieser Aufgabe gemachten Schlussfolgerungen sind der Schlüssel zur Analyse der Wahrscheinlichkeit, zwei Elemente zu einem Schlüssel zusammenzufassen. Dieses Problem kann weiter auf das Wahrscheinlichkeitsproblem von Bällen und Becken (Problem mit Bällen und Behältern) verallgemeinert werden, das wir für einen anderen Beitrag belassen werden.

Anwendung

Das Geburtstagsparadoxon ist nicht nur eine künstliche Aufgabe oder ein interessanter Partytrick, es hat viele reale Anwendungen. Persönlich glaube ich, dass die in den Beweisen verwendete Wahrscheinlichkeitsanalyse nützlich ist, um andere Aufgaben zu analysieren, an denen die Randomisierung beteiligt ist. Dies betrifft insbesondere die Entwicklung kryptografischer Hash-Funktionen. Wir werden sehen, wie nützlich die oben durchgeführte Analyse sein kann, um Hash-Funktionen mit Schutz vor Angriffen von „Geburtstagen“ zu erstellen.

Definieren wir zunächst, was eine Hash-Funktion ist. Hash-Funktion $$$h: U \ rightarrow [0, m-1]$ Ist eine Funktion, die eine Zuordnung aus einer Menge ausführt $$$U$ in einer Zahl im Bereich $$$[0, m-1]$ . Funktion $$$h$ definiert als $$$h (x) = x \ mod m$ - Beispiel einer Hash-Funktion von $$$\ mathbb {N} \ rightarrow [0, m-1]$ . Hash-Funktionen haben viele Verwendungsmöglichkeiten, insbesondere in Kombination mit der beliebten Hash-Tabellen-Datenstruktur. Es wird auch in der Kryptographie verwendet, wo eine bestimmte Art von Hash-Funktion verwendet wird, die als "kryptoraphische Hash-Funktion" bezeichnet wird.

Eine der vielen Eigenschaften, die eine kryptoraphische Hash-Funktion haben muss, ist die Kollisionsbeständigkeit. Es muss schwierig sein, zwei solche zu finden $$$u_1, u_2 \ in U$ so dass sie eine Kollision bilden, d.h. $$$h (u_1) = h (u_2)$ .

Wir werden uns auf den Widerstand gegen Kollisionen konzentrieren. Zunächst werde ich erklären, warum es eine wünschenswerte Eigenschaft ist. Dazu betrachten wir zunächst digitale Signaturen.

In der Vergangenheit verwendeten Personen und Organisationen Unterschriften und Siegel, um Dokumente zu „signieren“. In letzter Zeit gab es einen Übergang zu elektronischen oder digitalen Signaturen. Eine digitale Signatur muss drei grundlegende Eigenschaften erfüllen.

1. Wenn Sie ein Dokument signieren, müssen Sie überprüfen können, wer das Dokument signiert hat.
2. Nach der Unterzeichnung des Dokuments sollte niemand in der Lage sein, es zu fälschen.
3. Die Person, die das Dokument unterschrieben hat, kann die Unterzeichnung des Dokuments später nicht widerlegen.

Eine digitale Signatur ist eine Möglichkeit, die Wahrheit eines Dokuments oder einer Nachricht nachweislich zu überprüfen. Eine digitale Signatur stellt sicher, dass die empfangene Nachricht von einem bekannten Absender erstellt und nicht geändert wurde.

Nehmen wir an, wir haben ein Dokument $$$m$ . Wie unterschreiben wir es?

Jeder Benutzer / jede Organisation verfügt über einen eindeutigen privaten Schlüssel $$$p_k$ und öffentlicher Schlüssel $$$pub_k$ . Sie verwenden die Signaturfunktion, um ein Dokument mit ihrem eigenen privaten Schlüssel zu signieren. Eine digitale Signatur kann jedoch nur eine kleine Anzahl von Dokumenten signieren. Der Umfang der Signaturfunktion ist gering. Eine Möglichkeit, dieses Problem zu lösen, besteht darin, ein kleineres Dokument zu erstellen, das das Originaldokument darstellt, jedoch in einer viel kleineren Größe. Am häufigsten wird eine Hash-Funktion auf dieses große Dokument angewendet. Eine Hash-Funktion wird verwendet, um es von einem großen Raum auf einen kleineren abzubilden, und das Ergebnis einer solchen Operation wird als "Fingerabdruck" bezeichnet. Die Signatur verwendet den Fingerabdruck und den privaten Schlüssel, um die Signatur zu erstellen. Das Verfahren kann wie folgt beschrieben werden:

1. Holen Sie sich den privaten Schlüssel $$$p_k$ .
2. Hash ein Dokument $$$m$ und bekommen $$$h (m)$ .
3. Zeichen $$$h (m)$ mit dem privaten Schlüssel $$$p_k$ .
4. Wir senden $$$sign (h (m), p_k)$ und öffentlicher Schlüssel $$$pub_k$ Jeder, der das Dokument bestätigen möchte.

Wer hat $$$sign (h (m), p_k))$ und öffentlicher Schlüssel, kann überprüfen, ob das Dokument wirklich ist $$$m$ von der richtigen Person unterschrieben.

Problem: Angenommen, die Angreiferin Eva hat zwei Dokumente gefunden $$$m, m '$ wo $$$m$ - Dies ist der vorliegende Vertrag, und $$$m '$ - ein betrügerisches Dokument, so dass $$$h (m) = h (m ')$ . Angenommen, Eva weiß im Voraus, dass Alice nur unterschreiben wird $$$m$ , aber nicht $$$m '$ . Vor dem Signieren wird eine kryptografische Hash-Funktion auf das Dokument angewendet $$$h$ . Eve geht zu Alice und bittet sie, ein Dokument zu unterschreiben $$$m$ unter Verwendung der oben beschriebenen Sequenz. Nun kann Eve behaupten, Alice habe ein betrügerisches Dokument unterschrieben $$$m '$ , weil $$$h (m) = h (m ')$ . Alice wird in keiner Weise beweisen können, dass sie nicht unterschrieben hat $$$m '$ .

Im obigen Beispiel $$$h$ Es stellte sich heraus, dass es sich um eine kollisionssichere Funktion handelt, sodass Eve zwei eingehende Datensätze mit demselben Wert finden konnte. Eve konnte behaupten, dass Alice unterschrieben hatte $$$m '$ obwohl sie tatsächlich nur unterschrieb $$$m$ . Dies unterstreicht die Bedeutung der Kollisionsbeständigkeit und zeigt, warum digitale Signaturen anfällig sind, wenn die Hash-Funktion instabil ist.

Lass $$$h: U \ rightarrow [0, m-1]$ wird eine Hash-Funktion sein. Angenommen, die Eingabedaten werden zufällig gleichmäßig und unabhängig in eines der Elemente gehasht $$$m$ .

Die Aufgabe des "Geburtstag" -Angriffs besteht darin, die geringste Anzahl von Elementen zu finden $$$n$ was mit gehasht werden kann $$$h$ so dass wir zwei Elemente finden können $$$x, y \ in U$ bei denen $$$h (x) = h (y)$ .

Wenn der Angreifer „Geburtstage“ angreift, nimmt er zufällig auf $$$x \ in U$ und Paare halten $$$(x, h (x))$ . Ein Angreifer wählt diese Paare wiederholt aus und speichert sie, bis er zwei Werte gefunden hat $$$x, y$ bei denen $$$h (x) = h (y)$ . Wir müssen bestimmen, wie oft der Angreifer diesen Vorgang wiederholen muss, bis er eine Kollision findet.

Um den Angriff auf „Geburtstage“ zu analysieren, können Sie dieselben Prinzipien verwenden, die wir für das Geburtstagsparadoxon verwendet haben. Bei dem Angriff "Geburtstage" $$$m$ bezeichnet die Anzahl der Tage in einem Jahr und $$$U$ ähnlich wie Menschen, die einen Raum betreten. Menschen werden an ihren Geburtstagen gehasht, was eine der Bedeutungen sein kann. $$$m$ . Nehmen wir an, wir müssen eine Kollision mit einer Wahrscheinlichkeit von 99% finden. Wir müssen wissen, was das kleinste ist $$$n$ , in dem der Hash zweier Werte einen Geburtstag hat (in der Welt der Hash-Funktionen bedeutet dies, dass zwei Eingabedatensätze in denselben Wert gehasht werden).

Das haben wir vorher gezeigt $$$\ Pr [A_n] \ ungefähr e ^ {\ frac {-n ^ 2} {2m}}$

Wir wollen fragen $$$\ Pr [\ overline {A} _n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ , also $$$\ Pr [A_n] \ ungefähr e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ .

$$$$ display $$ \ begin {Gleichung *} \ 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 {Gleichung *} $$ display $$

Die oben gezeigte Analyse zeigt, dass Kollisionen in Hash-Funktionen mit einem Größenintervall abgerufen werden müssen $$$m$ Ein Angreifer muss ungefähr einheitlich und unabhängig hashen $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ für eine fast vollständige Garantie (99% Wahrscheinlichkeit), dass zwei Elemente mit demselben Wert gehasht werden.

Angenommen, wir möchten eine Kollision mit einer Wahrscheinlichkeit von 50% erhalten. dann brauchen wir $$$n = \ sqrt {2 m \ ln 2}$ . Die wichtige Schlussfolgerung hier ist, dass wir die Reihenfolge hashen müssen, um eine Kollision mit einer Wahrscheinlichkeit von mehr als 0,5 zu erhalten $$$\ sqrt {m}$ Elemente. Dies steht im Einklang mit unserer vorherigen Analyse für $$$m = 365$ , weil $$$\ sqrt {2 \ ln 2 \ cdot 365}$ ungefähr gleich 23.

Zusätzliche Aufgaben

1. Haben $$$n$ von Menschen $$$m$ Tage und eine bestimmte Anzahl $$$k$ Finden Sie die Wahrscheinlichkeit, dass genau $$$k$ Leute haben den gleichen Geburtstag.
2. Lassen Sie uns die obige Aufgabe ein wenig transformieren. Nehmen wir an, wir haben $$$m$ Tage und eine bestimmte Anzahl $$$k$ . Was wird der kleinste Wert sein $$$n$ bei denen nicht weniger $$$k$ Menschen haben den gleichen Geburtstag mit einer Wahrscheinlichkeit von mindestens 0,5? Können Sie diese Aufgabe mit beliebiger Wahrscheinlichkeit verallgemeinern? $$$p> 0$ ?
3. Angenommen, wir haben 100 Zahlen von 1 bis 100 sowie eine Maschine, die eine Zufallszahl von 1 bis 100 in einer einheitlichen und zufälligen Reihenfolge errät. Wie oft müssen wir die Maschine wie erwartet verwenden, damit die Maschine alle Zahlen von 1 bis 100 errät?
4. Können Sie diese Aufgabe auf eine beliebige verallgemeinern? $$$n$ ?
5. Angenommen, wir haben eine Hash-Funktion, die Elemente in einem Speicherbereich zufällig gleichmäßig anzeigt. Gesamtflächen lassen $$$m$ . Wie viele Elemente $$$n$ Müssen wir unserer Datenstruktur mathematische Erwartungen hinzufügen, damit in jeder Region mindestens zwei Elemente gehasht werden?