Das Geburtstagsparadoxon

Stellen Sie sich vor, Sie sind an einer Party mit 23 Gästen. Irgendwann ruft jemand in die Runde: "Wetten, dass zwei von uns am gleichen Tag Geburtstag haben?"

Sie überschlagen kurz im Kopf: Ein Jahr hat 365 Tage, wir sind nur 23 Leute... Sollten Sie die Wette annehmen?

Erst mal schätzen!

Bevor wir irgendetwas rechnen: Was sagt Ihr Bauchgefühl?

Kurz innehalten

Notieren Sie sich Ihre Antwort — wir lösen sie erst am Ende der Seite auf. Bis dahin gilt: nicht googeln, sondern selbst ausrechnen. Sie haben dafür gleich das perfekte Werkzeug: Python.

Die Mathematik dahinter

Wie packt man so eine Frage an? Direkt auszurechnen, dass irgendwo in der Gruppe zwei Personen am gleichen Tag Geburtstag haben, ist kompliziert — es gibt unzählige Kombinationen, wer mit wem zusammenfallen könnte.

Der Trick: Wir rechnen das Gegenteil aus — die Wahrscheinlichkeit, dass alle verschiedene Geburtstage haben. Davon nehmen wir dann eins minus.

Gehen wir Person für Person durch (365 Tage, alle gleich wahrscheinlich):

• Person 1 hat irgendeinen Geburtstag — kein Problem, Wahrscheinlichkeit $\frac{365}{365}$.
• Person 2 muss einen anderen Tag haben: $\frac{364}{365}$.
• Person 3 muss von beiden verschieden sein: $\frac{363}{365}$.
• Person 4: $\frac{362}{365}$ — und so weiter.

Alle Brüche werden multipliziert (jede Bedingung muss gleichzeitig erfüllt sein):

Auf dem Papier ist dieses Produkt für grössere $n$ mühsam — für 23 Personen müssten Sie 22 Brüche von Hand multiplizieren. Zum Glück haben Sie etwas Besseres als Papier.

Die Challenge: Rechnen Sie es aus 🎂

Schreiben Sie eine Funktion wahrscheinlichkeit(n), die für n Personen die Wahrscheinlichkeit zurückgibt, dass mindestens zwei davon am gleichen Tag Geburtstag haben — als Dezimalzahl zwischen 0 und 1.

Tipps zum Vorgehen

1. Starten Sie mit einer Variable produkt = 1.0.
2. Multiplizieren Sie mit einer Schleife nacheinander die Brüche $\frac{364}{365}$, $\frac{363}{365}$, $\frac{362}{365}$, ... auf — für n Personen sind das n - 1 Brüche.
3. Überlegen Sie sich, wie Sie den Zähler des Bruchs aus der Schleifenvariable berechnen können.
4. Geben Sie am Schluss 1 - produkt zurück.

Berechnen Sie anschliessend mit Ihrer Funktion die Wahrscheinlichkeit für 23 Personen — und vergleichen Sie mit Ihrer Schätzung vom Anfang. Probieren Sie auch andere Werte aus: Ab wie vielen Personen knackt die Wahrscheinlichkeit die 50 %? Ab wann 90 %?

def wahrscheinlichkeit(n):
    # Ihr Code hier
    pass

print(wahrscheinlichkeit(23))

Die Auflösung 🎉

Haben Sie es ausgerechnet? Dann wissen Sie es jetzt: Schon bei 23 Personen liegt die Wahrscheinlichkeit über 50 % — die Wette von der Party hätten Sie besser nicht angenommen. Hier die Übersicht:

In fast jeder Schulklasse gibt es also mit grosser Wahrscheinlichkeit ein Geburtstags-Duo. Probieren Sie es gleich aus — fragen Sie in die Runde!

Warum die Intuition versagt

Die meisten Menschen tippen auf 183 Personen — die Hälfte von 365 fühlt sich logisch an. Der Denkfehler: Unser Bauch vergleicht unbewusst eine Person gegen alle anderen — das wären bei 23 Personen nur 22 Vergleiche. Aber relevant sind die Paare: Bei 23 Personen gibt es

mögliche Paare — und jedes einzelne Paar ist eine Chance auf eine Kollision. 253 Chancen mit je $\frac{1}{365}$ Trefferwahrscheinlichkeit: Plötzlich wirken 50 % völlig plausibel.

Zusatz: Dasselbe mit Rekursion 🌀

Bis jetzt haben Sie Wiederholungen immer mit Schleifen gelöst. Es gibt aber noch einen zweiten, ganz anderen Weg: Rekursion — eine Funktion, die sich selbst aufruft.

Ein Beispiel: Countdown

def countdown(n):
    if n == 0:
        print("Start! 🚀")
    else:
        print(n)
        countdown(n - 1)   # Die Funktion ruft sich selbst auf!

countdown(5)

Führen Sie den Code aus und verfolgen Sie, was passiert: countdown(5) druckt die 5 und ruft countdown(4) auf. Diese druckt die 4 und ruft countdown(3) auf — und so weiter, bis countdown(0) erreicht ist und die Kette stoppt.

Jede Rekursion braucht zwei Zutaten:

1. Basisfall: Der einfachste Fall, der ohne weiteren Selbstaufruf beantwortet wird (hier: n == 0). Ohne Basisfall ruft sich die Funktion endlos selbst auf — das rekursive Gegenstück zur Endlosschleife.
2. Rekursionsschritt: Das Problem wird ein Stück kleiner gemacht und an die Funktion selbst weitergereicht (hier: countdown(n - 1)).

Die Challenge: Geburtstagsparadoxon rekursiv

Auch unsere Geburtstagsrechnung hat eine natürlich rekursive Struktur. Nennen wir $V(n)$ die Wahrscheinlichkeit, dass $n$ Personen alle verschiedene Geburtstage haben:

• Basisfall: $V(1) = 1$ — eine einzelne Person hat garantiert keinen Geburtstagszwilling.
• Rekursionsschritt: $V(n) = V(n-1) \cdot \frac{365 - (n-1)}{365}$ — die ersten $n-1$ Personen müssen verschieden sein, und die $n$-te Person muss einen der noch freien $365-(n-1)$ Tage erwischen.

Schreiben Sie eine rekursive Funktion alle_verschieden(n), die $V(n)$ zurückgibt — also die Wahrscheinlichkeit, dass n Personen lauter verschiedene Geburtstage haben. Verwenden Sie keine Schleife: Die Funktion soll sich selbst aufrufen.

def alle_verschieden(n):
    # Ihr Code hier (ohne Schleife!)
    pass

print(alle_verschieden(23))       # ungefähr 0.493
print(1 - alle_verschieden(23))   # ungefähr 0.507 — wie vorher!

Wozu Rekursion?

Alles, was Sie rekursiv lösen können, geht auch mit einer Schleife — und umgekehrt. Manche Probleme sind aber rekursiv viel natürlicher zu formulieren: Dateisysteme durchsuchen (Ordner enthalten Ordner enthalten Ordner...), Fraktale zeichnen, Spielbäume in Schach-Programmen durchrechnen. Rekursion ist eines der mächtigsten Denkwerkzeuge der Informatik — Sie werden ihr wieder begegnen.