Über das Geburtstagsparadoxon | Paare, die Rechnung und Geburtstagsangriffe

Das Paradoxon

Fragt man, wie viele Gäste eine Party braucht, damit zwei von ihnen wahrscheinlich am selben Tag Geburtstag haben, sagen die meisten etwa 180, die Hälfte von 365. Die richtige Antwort ist 23: Dann liegt die Wahrscheinlichkeit bei 50,7 %. Bei 57 Gästen sind es 99 %. Paradoxon heißt es nicht, weil es widersprüchlich wäre, sondern weil es unserer Intuition so stark widerspricht.

Warum die Intuition versagt

In einem Raum denken wir unbewusst von uns selbst aus: Wie groß ist die Wahrscheinlichkeit, dass jemand am selben Tag Geburtstag hat wie ich? Bei 365 Tagen ist diese Wahrscheinlichkeit klein. Beim Paradoxon geht es aber um alle möglichen Paare im Raum, nicht um einen Treffer mit einer bestimmten Person: A und B, B und C, A und C und so weiter. Mit 23 Personen kann man 253 verschiedene Paare bilden, und jedes davon könnte am selben Tag Geburtstag haben.

Paare wachsen mit dem Quadrat

n Personen bilden n × (n − 1) / 2 Paare: 10 Personen bilden 45 Paare, 23 bilden 253, 57 bilden 1.596 und 100 bilden 4.950. Jedes Paar hat mit Wahrscheinlichkeit 1/365 gemeinsam Geburtstag, also ergeben 253 Paare im Mittel 253/365 ≈ 0,69 Paare mit gemeinsamem Geburtstag. Verdoppelt man die Gruppe, vervierfacht sich ungefähr die Zahl der Paare, und deshalb schießt die Wahrscheinlichkeit eines gemeinsamen Geburtstags nach oben.

Die Rechnung Schritt für Schritt

Am einfachsten berechnet man die Wahrscheinlichkeit, dass alle an verschiedenen Tagen Geburtstag haben, und zieht sie von 100 % ab. Die erste Person belegt einen beliebigen Tag. Die zweite Person hat mit Wahrscheinlichkeit 364/365 nicht denselben Geburtstag. Die dritte unterscheidet sich mit Wahrscheinlichkeit 363/365 von den ersten beiden, und so weiter. Für 23 Personen:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3 %

Da die Wahrscheinlichkeit, dass alle an verschiedenen Tagen Geburtstag haben, 49,3 % beträgt, hat das Gegenereignis, mindestens ein gemeinsamer Geburtstag, die Wahrscheinlichkeit 100 % − 49,3 % = 50,7 %.

Jemand mit Ihrem Geburtstag

Ob jemand Ihren eigenen Geburtstag teilt, ist eine andere Frage. Jede der anderen n − 1 Personen verfehlt Ihren Geburtstag mit Wahrscheinlichkeit 364/365, also ist die Wahrscheinlichkeit, dass jemand ihn hat, 1 − (364/365)ⁿ⁻¹. Bei 23 Personen sind das nur 5,9 %, und Sie brauchen 253 andere, bevor 50 % überschritten werden. Nur 22 der 253 Paare in einer Gruppe von 23 schließen Sie ein.

Die Wurzelregel und Geburtstagsangriffe

Bei N gleich wahrscheinlichen Werten wird eine Wiederholung nach etwa 1,2 × √N Ziehungen wahrscheinlich: √365 ≈ 19, und 1,2 × 19 ≈ 23. Das ist in der Computersicherheit sehr wichtig. Angreifer nutzen Geburtstagsangriffe, um zwei Eingaben mit demselben kryptografischen Hashwert zu finden, eine Kollision, etwa um eine digitale Signatur zu fälschen. Dank des Geburtstagsparadoxons brauchen sie weit weniger Versuche, als die Intuition vermuten lässt: etwa 2⁶⁴ statt 2¹²⁸ bei einem 128-Bit-Hash. Deshalb haben moderne Hashfunktionen wie SHA-256 lange Ausgaben.

In PictorX erkunden

Öffnen Sie das Geburtstagsparadoxon, und eine Gruppe von 23 Personen bildet sich auf einem Kreis, eine Person nach der anderen. Jede neue Person fügt eine Linie zu jeder bereits anwesenden hinzu, und die Beschriftung zählt die Paare. Ihre Geburtstage fallen in einen Kalender, und ein Tag mit zwei oder mehr leuchtet auf. Darunter steht die Rechnung für die Gruppengröße neben dem Anteil der getesteten Gruppen mit einem gemeinsamen Geburtstag, und das Diagramm zeigt die Wahrscheinlichkeit für jede Gruppengröße, für zwei beliebige Personen und für jemanden mit Ihrem Geburtstag. Fügen Sie Personen einzeln hinzu, wählen Sie 2 bis 366 Personen, testen Sie bis zu 100.000 Gruppen mit bis zu 10.000 pro Sekunde, oder testen Sie alle Gruppengrößen und sehen Sie zu, wie die Punkte die Kurve nachzeichnen.

Häufig gestellte Fragen

Was ist das Geburtstagsparadoxon?

Die überraschende Tatsache, dass in einer Gruppe von nur 23 Personen die Wahrscheinlichkeit, dass zwei von ihnen am selben Tag Geburtstag haben, über 50 % liegt: 50,7 %.

Warum reichen 23 Personen?

Weil 23 Personen 253 Paare bilden, und jedes Paar ist eine Chance auf einen gemeinsamen Geburtstag. Wir neigen dazu, nur die 22 Paare zu zählen, zu denen wir selbst gehören.

Wie viele Personen braucht man für eine Wahrscheinlichkeit von 99 %?

57. Bei 70 Personen liegt die Wahrscheinlichkeit bei 99,9 %, und bei 366 Personen ist ein gemeinsamer Geburtstag sicher, weil es nur 365 Tage gibt.

Was ist ein Geburtstagsangriff?

Ein Angriff auf eine kryptografische Hashfunktion, der das Geburtstagsparadoxon ausnutzt: Unter etwa √N zufälligen Eingaben haben wahrscheinlich zwei denselben Hashwert von N möglichen Werten, also findet man Kollisionen weit früher als beim Versuch, einen vorgegebenen Hashwert zu treffen.

Ändert sich das Ergebnis mit echten Geburtstagen?

Kaum. Echte Geburtstage sind nicht perfekt gleichmäßig über das Jahr verteilt, und eine ungleichmäßige Verteilung macht einen gemeinsamen Geburtstag etwas wahrscheinlicher. Der 29. Februar, den es nur alle vier Jahre gibt, macht fast keinen Unterschied.

Verwandte Tools

Das Geburtstagsparadoxon

In einer Gruppe von 23 Personen liegt die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, bei 50,7 %, bei 57 Personen sind es 99 %. Sehen Sie alle 253 Paare, den Kalender und die Kurve, und testen Sie Tausende zufälliger Gruppen in Ihrem Browser.

Das Ziegenproblem

Das Ziegenproblem zum Ausprobieren: Wählen Sie eine von drei Türen, sehen Sie zu, wie Monty eine Tür mit einer Ziege öffnet, und bleiben oder wechseln Sie dann. Spielen Sie selbst oder lassen Sie den Computer 1.000 Spiele spielen: Wechseln gewinnt in zwei von drei Fällen.