Das Geburtstagsparadoxon: Warum 23 Personen für einen Treffer genügen

Bei der WM 2014 machten Journalisten den Test mit allen 32 Kadern. Jeder Kader hatte genau 23 Spieler, und in 16 der 32, also der Hälfte, hatten mindestens zwei Spieler am selben Tag Geburtstag. Niemand hatte das arrangiert. Es ist schlicht das, was die Zahl 23 tut.

Das ist das Geburtstagsparadoxon: In einem Raum mit 23 Personen ist ein gemeinsamer Geburtstag wahrscheinlicher als keiner. Es gibt 365 mögliche Geburtstage und nur 23 Personen, die Behauptung klingt also absurd, und diese Reaktion ist nahezu universell. Aber das Ergebnis ist kein Trick, keine statistische Illusion und hängt an keinem Kleingedruckten. Es ist ein kurzes Zählargument, und sobald du siehst, welche Zählung die Intuition anstelle der richtigen durchführt, löst sich das Paradoxon in etwas beinahe Offensichtliches auf.

Die Behauptung, sorgfältig formuliert

Nimm 23 Personen, deren Geburtstage unabhängig sind und mit gleicher Wahrscheinlichkeit auf jeden der 365 Tage fallen, den 29. Februar lassen wir vorerst beiseite. Die Behauptung lautet:

Die Wahrscheinlichkeit, dass mindestens zwei von ihnen am selben Tag Geburtstag haben, beträgt 50.7%, etwas besser als ein Münzwurf.

Zwei Details sind wichtig. Erstens geht es darum, dass irgendwelche zwei Personen übereinstimmen, nicht darum, eine bestimmte Person zu treffen. Zweitens bedeutet "gemeinsamer Geburtstag" denselben Tag im Jahr, etwa den 14. März, nicht denselben Tag samt Jahr. Beide Details klingen nebensächlich. Eines davon ist, wie wir sehen werden, das gesamte Paradoxon.

Der Beweis ist bloßes Zählen

Die direkte Frage, wie wahrscheinlich es ist, dass irgendjemand irgendjemanden trifft, ist frontal schwer anzugreifen, weil Treffer auf viele überlappende Arten zustande kommen können. Die Wahrscheinlichkeitsrechnung hat dafür einen Standardzug: Berechne die Wahrscheinlichkeit, dass nichts passiert, und ziehe sie von 1 ab. Warum dieser Zug erlaubt ist, erklärt von Grund auf Wahrscheinlichkeit intuitiv verstehen.

Das ist der ganze Beweis: Zähle die Paare, um zu sehen, warum ein Treffer plausibel ist, und multipliziere dann 23 Brüche, um zu sehen, wie plausibel genau. Keine schwere Maschinerie, nichts, das man glauben müsste. Jeder Schritt lässt sich mit einem Taschenrechner nachprüfen.

Und die Kurve klettert schnell weiter. Bei 30 Personen liegt die Trefferwahrscheinlichkeit bei 70.6%. Bei 50 Personen sind es 97.0%. Bei 70 Personen 99.9%: Ein gemeinsamer Geburtstag ist so gut wie garantiert, während 295 Tage des Jahres noch unberührt sind.

Wo die Intuition danebengreift

Das Geburtstagsparadoxon täuscht Menschen zuverlässig, und es täuscht sie auf eine ganz bestimmte, diagnostizierbare Weise: Sie beantworten die falsche Frage.

Hör dir das Rätsel an, und dein Kopf ersetzt es still durch eine Version mit dir in der Hauptrolle. Wie stehen die Chancen, dass hier jemand meinen Geburtstag trifft? Diese Frage hat tatsächlich eine kleine Antwort. In einem Raum mit 23 gibt es nur 22 andere Personen, jede trifft dich mit Wahrscheinlichkeit 1/365, und die Gesamtwahrscheinlichkeit, dass irgendjemand dich trifft, liegt bei etwa 6%. Ginge es im Rätsel um deinen Geburtstag, hätten die Skeptiker recht.

Aber im Rätsel geht es um irgendeinen Treffer. Du gegen jeden der anderen: 22 Paare. Aber auch Person 2 gegen Person 3, Person 7 gegen Person 19 und jede andere Kombination, die dich überhaupt nicht betrifft: 231 weitere Paare, insgesamt 253. Die Intuition zählt die 22 Vergleiche, die sie von innen sehen kann, und ist strukturell blind für die 231, an denen sie nicht beteiligt ist. Das Paradoxon besteht nicht darin, dass sich Wahrscheinlichkeit seltsam verhält. Es besteht darin, dass ein Raum mit 23 Personen elfmal mehr Vergleiche enthält, als jede einzelne Person erlebt.

Es gibt eine hübsche Art zu sehen, wie groß diese Lücke ist. Für eine 50%-Chance, dass jemand ausgerechnet dich trifft, reichen 22 andere bei weitem nicht: Du brauchst 253 Personen außer dir selbst. Die Anzahl der anderen, die man für einen festen Geburtstag braucht, ist dieselbe wie die Anzahl der Paare unter 23 Personen. Das ist kein Zufall, es sind die beiden Fragen, die von derselben Arithmetik gelöst werden, und es misst präzise, wie sehr die Sichtweise "mein Geburtstag" die Lage unterschätzt.

Das Kleingedruckte, das die Antwort ehrlich macht

Die Rechnung setzte 365 gleich wahrscheinliche Geburtstage und keinen Schalttag voraus. Beide Annahmen sind in der echten Welt falsch, also ist es fair zu fragen, ob die 50.7% den Kontakt mit der Realität überleben.

Sie tun es, und die Realität hilft sogar. Den 29. Februar als seltenen 366. Tag hinzuzunehmen drückt die Wahrscheinlichkeit um einen Hauch nach unten, viel zu wenig, um die Schwelle von der 23 wegzubewegen. Ungleich verteilte Geburtstage schieben in die andere Richtung: Echte Geburtsdaten zeigen saisonale Spitzen, bestimmte Monate sind verlässlich voller als andere. Jede solche Ungleichheit macht Kollisionen wahrscheinlicher, denn Wahrscheinlichkeit auf beliebte Tage zu bündeln ist genau das, wovon Kollisionen leben. Das gleichverteilte Modell ist die härteste denkbare Bedingung für das Paradoxon, und es schafft die 50% trotzdem.

Bei dieser Robustheit lohnt es sich innezuhalten, denn sie ist das Gegenteil davon, wie sich paradox angehauchte Rätsel sonst verhalten. Das Ziegenproblem etwa ist berüchtigt empfindlich gegenüber seinem Kleingedruckten: Ändere, was der Moderator weiß, und die Antwort ändert sich. Das Geburtstagsparadoxon ist das robuste Geschwisterkind. Jede realistische Abweichung von den Lehrbuchannahmen schiebt die Wahrscheinlichkeit nach oben, die Überraschung übersteht also jede Spitzfindigkeit.

Vom Partytrick zum Knacken von Hashfunktionen

Das Geburtstagsparadoxon würde sich schon als Partywette bezahlt machen, aber es hat auch einen ernsten Job. In der Kryptographie bestimmt es den Preis für das Finden von Kollisionen, und eine ganze Angriffsstrategie ist nach ihm benannt.

Eine Hashfunktion presst jede Eingabe in einen Fingerabdruck fester Größe, und Sicherheit hängt oft davon ab, dass niemand zwei verschiedene Eingaben mit demselben Fingerabdruck findet. Angenommen, die Fingerabdrücke haben 128 Bit, es gibt also 2 hoch 128 Möglichkeiten, eine astronomisch große Zahl. Eine Eingabe zu erraten, die einen bestimmten Fingerabdruck trifft, braucht tatsächlich in der Größenordnung von 2 hoch 128 Versuchen, für immer aussichtslos. Aber ein Angreifer, der nur irgendeine Kollision will, irgendwelche zwei übereinstimmenden Eingaben, spielt das Geburtstagsspiel: Erzeuge zufällige Eingaben, und nach der Quadratwurzelregel ist eine Kollision nach ungefähr 2 hoch 64 Versuchen zu erwarten. Das ist der Geburtstagsangriff, und 2 hoch 64 ist eine große Zahl, aber keine sichere; entschlossene Angreifer haben sie überschritten.

Das Paradoxon halbiert mit anderen Worten die effektive Stärke eines Hashes, gemessen in Bits. Deshalb verwenden Kryptographen, die 128 Bit Kollisionsresistenz wollen, Hashes mit 256-Bit-Ausgaben: Die Quadratwurzel von 2 hoch 256 ist 2 hoch 128, womit selbst die Geburtstagsabkürzung außer Reichweite liegt. Ein Muster, das entscheidet, wie viele Leute du zu einer Party einlädst, entscheidet auch, wie viele Bits deine Bankverbindung schützen, und es ist beide Male dieselbe Rechnung.

Probier es aus, denn es kostet nichts

Wie die besten Ergebnisse der Wahrscheinlichkeitsrechnung ist auch dieses billig zu testen. Jede Gruppe von etwa 25 Personen taugt dafür: ein Klassenzimmer, eine Büroetage, ein Mannschaftskader, eine Hochzeitsgästeliste. Frag alle nach ihrem Geburtstag und warte auf den Treffer. Eine einzelne Gruppe beweist natürlich nichts, in keine Richtung. Die Behauptung lautet 50.7%, nicht Gewissheit, die Wette verliert also fast die Hälfte der Zeit.

Die überzeugende Version ist Wiederholung. Sportkader sind dafür ideal, weshalb die WM in Artikeln zum Geburtstagsparadoxon immer wieder auftaucht: Kader mit 23 Spielern sind das Experiment exakt an der Schwellengröße, fertig zusammengestellt und öffentlich. Prüfe zehn Kader, und du solltest in etwa fünf davon Treffer erwarten. Oder simuliere es: Ein paar Zeilen Code, die 23 Zufallszahlen von 1 bis 365 ziehen und auf Wiederholungen prüfen, zehntausendmal ausgeführt, landen auf den Bruchteil eines Prozents genau bei 0.507. Das Argument mit den 23 multiplizierten Brüchen macht eine präzise Vorhersage, die Welt stimmt ihr immer wieder zu, und es gibt wenige schnellere Wege, Wahrscheinlichkeit real werden zu spüren.

Das Zen davon

Das Geburtstagsparadoxon hat Bestand, weil es eine perfekte Miniatur eines allgemeinen Fehlermusters ist. Die Intuition bewertet Situationen aus einem einzigen Blickwinkel, deinem, und in kombinatorischen Situationen liegt der einzelne Blickwinkel um einen Faktor daneben, der mit der Menge wächst. Nichts am Zufall benimmt sich daneben. Der Fehler liegt vollständig darin, welche Frage stillschweigend beantwortet wird.

Und das Heilmittel ist dasselbe wie immer in der Wahrscheinlichkeitsrechnung: Weigere dich zu raten, und zähle. Zähle die Paare, und die Plausibilität erscheint. Multipliziere die Brüche, und die exakte Zahl fällt heraus. Dieselbe Zählung taucht dann unverändert im Entwurf kryptographischer Systeme wieder auf, was die stille Lektion des ganzen Themas ist: Ein Wahrscheinlichkeitsargument weiß nicht, ob es für eine Kneipenwette oder für die Absicherung des Internets verwendet wird.

Dreiundzwanzig Personen. Zweihundertdreiundfünfzig Chancen. Der Raum war nie so leer, wie er aussah.