Dies ist eine maschinelle Übersetzung; das englische Original ist maßgebend. Original lesen
Dreiundzwanzig Personen und der Zufall, den man erwarten sollte
Dreiundzwanzig Personen ergeben 253 Paare. Niemand rechnet je diese 253 aus, und genau das ist der alleinige Grund, warum sich die Antwort falsch anfühlt.
Befinden sich 23 Personen in einem Raum, liegt die Wahrscheinlichkeit, dass zwei von ihnen am selben Tag Geburtstag haben, bei 50,7 %. Bei 70 Personen beträgt sie 99,9 %.
Fast jeder schätzt eine viel zu hohe Zahl, und zwar deshalb, weil die falsche Frage gestellt wird. Der erste Impuls ist, an sich selbst zu denken: Wie hoch ist die Wahrscheinlichkeit, dass jemand hier an meinem Geburtstag Geburtstag hat? Das ist ein deutlich selteneres Ereignis, und man bräuchte etwa 253 Personen, damit sie die Hälfte übersteigt.
Die tatsächliche Frage betrifft jedoch irgendein beliebiges Paar. Und an Paaren mangelt es nicht.
Paare zählen, nicht Personen
Dreiundzwanzig Personen ergeben 23 × 22 ÷ 2 = 253 verschiedene Paare. Jedes Paar hat eine Chance von 1 zu 365 auf eine Übereinstimmung. Die Anzahl der Paare wächst mit dem Quadrat der Personenzahl, sodass eine Verdopplung der Personen im Raum die Möglichkeiten für einen Zufall vervierfacht.
Die exakte Berechnung verläuft umgekehrt — man bestimmt die Wahrscheinlichkeit, dass keine zwei Personen übereinstimmen. Das ist 365/365 × 364/365 × 363/365 × … über 23 Faktoren, was 0,493 ergibt. Eins minus diesen Wert ergibt 0,507.
Die allgemeine Regel, die man sich merken sollte
Bei N gleich wahrscheinlichen Möglichkeiten benötigt man ungefähr √N Ziehungen, bevor eine Wiederholung wahrscheinlicher wird als nicht. Für Geburtstage ist √365 ≈ 19, und mit der Konstante ergibt sich etwa 1,18 × √N ≈ 22,5. Nah genug an 23.
Quadratwurzel, nicht die Hälfte. Das ist die Zahl, bei der sich die Leute verschätzen — und zwar in der Weise, dass sie Zufälle für seltener halten, als sie tatsächlich sind.
Wo es aufhört, ein Partytrick zu sein
Hash-Kollisionen. Eine Hash-Tabelle mit tausend Plätzen beginnt nicht erst dann Kollisionen zu erzeugen, wenn sie sich tausend Einträgen nähert. Die ersten Kollisionen treten bereits bei etwa dreißig Einträgen auf. Deshalb kümmern sich Implementierungen von Hash-Tabellen vom allerersten Einfügen an um die Kollisionsbehandlung, und deshalb sagt die alleinige Messung des Belegungsfaktors wenig darüber aus, wie viele Sondierungsschritte ein Suchvorgang erfordert. Das Werkzeug Hash Table zeigt, dass Kollisionen viel früher auftreten als erwartet.
Kryptographie. Hier bestimmt die Quadratwurzel den Sicherheitsparameter. Um zwei verschiedene Dokumente mit demselben 64-Bit-Hashwert zu finden, benötigt man keine 2⁶⁴ Versuche, sondern etwa 2³² — ungefähr vier Milliarden, was eine Arbeit von wenigen Minuten ist. Das ist der Geburtstagsangriff, und deshalb muss eine Hashfunktion, die n Bits Kollisionsresistenz bieten soll, einen Ausgabewert von 2n Bits erzeugen. Aus diesem Grund geht man davon aus, dass 128-Bit-Hashes lediglich 64 Bits Kollisionsresistenz bieten, weshalb sie für Signaturen nicht mehr akzeptabel sind.
Zufälle deuten. Jedes ausreichend große Datenset enthält auffällige Koinzidenzen, und deren Anzahl skaliert mit den Paaren, nicht mit den Datensätzen. Zwei Personen in einer Stadt, die im Lotto gewinnen, eine Häufung einer Krankheit in einer Straße, zwei Lieder, die ähnlich klingen: Solche Ereignisse werden bei entsprechender Skalierung zu Beinahe-Gewissheiten, und jedes davon als einzeln unwahrscheinlich zu behandeln ist derselbe Rechenfehler, der bei Personen und Geburtstagen gemacht wird.
Die richtige Frage lautet nie: „Wie unwahrscheinlich ist dieser bestimmte Zufall?“, sondern: „Wie viele Möglichkeiten gab es für einen Zufall dieser Art?“ Diese beiden Zahlen unterscheiden sich um einen Faktor, der quadratisch wächst — was mehr als ausreicht, um aus einem Erstaunen eine Erwartung zu machen.
Zwei Einwände, die beide eine Antwort verdienen
„Geburtstage sind nicht gleichmäßig verteilt.“ Das sind sie tatsächlich nicht — auf der Nordhalbkugel gibt es im Spätsommer mehr Geburten, weniger am 25. Dezember und 29. Februar sowie einen sichtbaren Rückgang an Wochenenden aufgrund von geplanten Entbindungen. Aber eine Ungleichverteilung macht Übereinstimmungen immer wahrscheinlicher, nie unwahrscheinlicher: Klumpung konzentriert die Personen auf weniger effektive Tage. Die Annahme einer Gleichverteilung ist daher konservativ, und 23 ist wenn überhaupt eine leichte Überschätzung.
„Zwillinge und Personen, die zusammen gekommen sind.“ Räume in der Realität sind keine Zufallsstichproben. Ein Raum mit Geschwistern oder eine Schulklasse, die nach einem Stichtag zusammengestellt wurde, weist Korrelationen auf, die das Modell nicht berücksichtigt. Die Berechnung bildet einen Referenzwert für unabhängige Ziehungen — und wo Ziehungen nicht unabhängig sind, muss die Unabhängigkeit begründet werden, nicht die Arithmetik.
Die Faustregel für unterwegs
Gibt es N gleich wahrscheinliche Kategorien und man führt k Ziehungen durch, beträgt die erwartete Anzahl kollidierender Paare etwa k²/2N. Setzt man diesen Wert gleich eins, erhält man k ≈ √(2N) — dieselbe Quadratwurzel, ermittelt durch das Zählen erwarteter Kollisionen statt über Wahrscheinlichkeiten, und im Kopf leichter zu rechnen.
Für tausend Hash-Plätze: √2000 ≈ 45; man kann die erste Kollision also irgendwo in den Vierzigern erwarten. Für eine 32-Bit-Prüfsumme: 2¹⁶ = 65.536 Einträge, die eine Logdatei an einem Nachmittag erreicht. Für 365 Tage: 27, was nah genug an 23 liegt, sodass man der Schätzung vertrauen kann.
Man sollte sich angewöhnen, immer dann zur Quadratwurzel zu greifen, wenn man die Frage hört: „Wie hoch ist die Wahrscheinlichkeit für ein Duplikat?“, und zu erkennen, dass die Antwort viel früher eintrifft, als es die Größe des Raumes vermuten lässt. Das Werkzeug Birthday Paradox stellt die Kurve grafisch dar, und ihre Steilheit im Bereich von 20 bis 30 Personen lässt sich mit Worten kaum angemessen beschreiben.