Einführung
Frisch vom College schmeißt du eine große Party, um mit Freunden und Familie zu feiern.
Über 70 Leute sind gekommen, darunter dein leicht exzentrischer Onkel Ted.
In einem seiner üblichen Scherze wettet er mit dir um 100 £, dass mindestens zwei Personen im Raum am selben Tag Geburtstag haben.
Das klingt absurd: Es gibt viel mehr mögliche Geburtstage als Gäste. Also nimmst du die Wette selbstbewusst an.
Zu deinem Erstaunen hast du schon nach den Geburtstagen von nur 32 Gästen zwei Personen gefunden, die am selben Tag Geburtstag haben.
Du nimmst deine Niederlage an und drückst Onkel Ted seine 100 £ in die Hand, aber irgendetwas stimmt nicht.
Am nächsten Tag siegt die Neugier.
Eine kurze Websuche führt dich zum Geburtstagsparadoxon, das zeigt, dass bei nur 23 Personen die Wahrscheinlichkeit eines gemeinsamen Geburtstags über 50 % liegt.
Ah. Also deshalb war Onkel Ted so selbstsicher.
Entschlossen, das Blatt zu wenden, suchst du nach weiteren Paradoxien; beim nächsten Mal bist du diejenige, die die Wetten abschließt.
Das Geburtstagsparadoxon ist ein veridikales Paradoxon: Auch wenn es sich falsch anfühlt, ist es tatsächlich wahr.
Anleitung
Deine Aufgabe ist es, die Wahrscheinlichkeiten des Geburtstagsparadoxons zu schätzen.
Dazu musst du:
- Zufällige Geburtsdaten generieren.
- Prüfen, ob eine Sammlung zufällig generierter Geburtsdaten mindestens zwei mit demselben Geburtstag enthält.
- Die Wahrscheinlichkeit schätzen, dass mindestens zwei Personen in einer Gruppe denselben Geburtstag haben, und das für verschiedene Gruppengrößen.
Ein Geburtsdatum umfasst das vollständige Datum der Geburt (Jahr, Monat und Tag), während ein Geburtstag sich nur auf Monat und Tag bezieht, die sich jedes Jahr wiederholen.
Zwei Geburtsdaten mit demselben Monat und Tag entsprechen demselben Geburtstag.
Das Geburtstagsparadoxon geht von Folgendem aus:
- Es gibt 365 mögliche Geburtstage (keine Schaltjahre).
- Jeder Geburtstag ist gleich wahrscheinlich (Gleichverteilung).
Deine Implementierung muss diese Annahmen befolgen.
Spezifische Hinweise zu x86-64-Assembly
Die Funktion random_birthdates() sollte Datumsangaben mit den folgenden Eigenschaften erzeugen:
- Das Jahr sollte gültig sein.
Ein gültiges Jahr
y ist kein Schaltjahr und erfüllt 1600 <= y < 2129.
- Das Jahr ist gleichmäßig über den gesamten Bereich der gültigen Werte verteilt.
- Der Geburtstag ist gleichmäßig über alle 365 Tage des Jahres verteilt, sodass jeder Kalendertag gleich wahrscheinlich ist.
Beachte, dass das bedeutet, dass Monate nicht gleich wahrscheinlich sind: Ein Monat mit 31 Tagen ist wahrscheinlicher als einer mit 30 Tagen, und beide sind wahrscheinlicher als der Februar.
Sowohl die Verteilung des Jahres als auch die des Geburtstags wird mit einem Chi-Quadrat-Test geprüft, und zwar auf dem Niveau von p < 0,0001.
Das bedeutet: Wenn die Datumsangaben gemäß der Anleitung erzeugt werden, besteht eine Chance von weniger als 0,01 %, dass die erzeugte Werteverteilung den Test nicht besteht.
