Realizing Common Random Numbers: Event-Keyed Hashing for Causally Valid Stochastic Models

Die Arbeit zeigt, dass herkömmliche zustandsbehaftete Zufallszahlengeneratoren in agentenbasierten Modellen zu kausal inkonsistenten Gegenfaktoralvergleichen führen, wenn Eingriffe den Ausführungsfluss ändern, und schlägt als Lösung die Kombination von zählerbasierten Generatoren mit Ereignis-IDs vor, um eine kausal gültige Stochastik sicherzustellen.

Das Wesentliche

🎲 Das Problem: Wenn der Zufall den Plan verliert

Stellen Sie sich vor, Sie sind ein Wissenschaftler, der ein riesiges, digitales Spiel simuliert. In diesem Spiel gibt es Millionen von Spielern (Agenten), die Krankheiten bekommen, genesen oder geimpft werden. Sie wollen herausfinden: „Was wäre passiert, wenn wir alle geimpft hätten, verglichen mit dem Szenario, in dem niemand geimpft wurde?"

Um das genau zu berechnen, nutzen Sie einen Trick namens „Gemeinsame Zufallszahlen" (Common Random Numbers).
Stellen Sie sich vor, Sie spielen das Spiel zweimal:

1. Szenario A (Ohne Impfung): Sie werfen einen Würfel für jeden Spieler, um zu entscheiden, ob er krank wird.
2. Szenario B (Mit Impfung): Sie wollen das exakt gleiche Spiel nochmal spielen, nur mit dem Unterschied, dass die Impfung wirkt.

Der Trick ist: Sie wollen, dass jeder einzelne Würfelwurf in Szenario B genau dem Würfelwurf in Szenario A entspricht. Nur so können Sie fair vergleichen: „Hätte Person X ohne Impfung krank geworden sein? Ja. Wird sie mit Impfung krank? Nein." Der Unterschied liegt also nur an der Impfung, nicht daran, dass das Glück heute anders war.

🚂 Der Fehler: Der Zug, der aus dem Takt gerät

Das Problem liegt in der Art und Weise, wie Computer Zufallszahlen erzeugen. Die meisten nutzen einen Zustandsbehafteten Generator (Stateful PRNG).

Die Analogie des Zugfahrplans:
Stellen Sie sich den Zufallsgenerator als einen Zug vor, der auf einer Schiene fährt. Er hat einen Fahrplan mit nummerierten Haltestellen (Zufallszahlen): 1, 2, 3, 4, 5...

• In Szenario A (ohne Impfung) passiert Person 1 krank. Der Zug hält an Station 1 (Krankheit prüfen), dann an Station 2 (Wartezeit berechnen), dann an Station 3 (Person 2 prüfen).
• In Szenario B (mit Impfung) ist Person 1 gesund, weil die Impfung wirkt. Der Zug hält an Station 1 (Krankheit prüfen). Aber da Person 1 gesund ist, überspringt der Zug Station 2 (keine Wartezeit nötig!).

Das Desaster:
Jetzt ist der Zug in Szenario B bei Station 2 angekommen, um Person 2 zu prüfen. Aber in Szenario A war Person 2 bei Station 3!
Person 2 bekommt also in Szenario A eine andere „Zufallszahl" (Station 3) als in Szenario B (Station 2).
Das Ergebnis: Sie vergleichen nicht mehr „Person 2 mit Impfung" gegen „Person 2 ohne Impfung". Sie vergleichen „Person 2 mit Impfung" gegen „Person 2 mit einem ganz anderen Schicksal". Der Vergleich ist kaputt, weil der Zugplan durch die Impfung verschoben wurde.

Die Autoren nennen dies „Abhängigkeit vom Ausführungsweg". Das Computerprogramm vergisst, welches Ereignis es gerade betrachtet, und schaut nur, wie viele Zahlen es schon verbraucht hat.

🔑 Die Lösung: Der Schlüssel für jedes Ereignis

Die Forscher schlagen eine neue Methode vor: Ereignis-gesteuerte Hashing (Event-Keyed Hashing).

Die neue Analogie: Der Schlüsselbund
Statt eines Zuges, der nur weiterfährt, geben wir jedem einzelnen Ereignis einen eigenen, unveränderlichen Schlüssel.

• Die Frage „Wird Person 2 krank?" bekommt einen Schlüssel namens Person2_Krankheit.
• Die Frage „Wie lange dauert die Krankheit von Person 1?" bekommt den Schlüssel Person1_Wartezeit.

Es spielt keine Rolle, ob Person 1 krank wird oder nicht.

• Wenn Person 1 krank wird, nutzen wir den Schlüssel Person1_Wartezeit.
• Wenn Person 1 gesund bleibt, nutzen wir niemals diesen Schlüssel. Aber: Der Schlüssel für Person 2 (Person2_Krankheit) bleibt immer derselbe!

Wir nutzen einen speziellen Zufallsgenerator (einen „Counter-based PRNG"), der wie ein Schlossschloss funktioniert:

• Schloss = Schlüssel + Geheimcode (Seed)
• Egal in welcher Reihenfolge Sie die Schlösser öffnen, Schloss(Person2_Krankheit) öffnet immer dasselbe Schloss und zeigt immer dasselbe Ergebnis an.

🌟 Warum ist das wichtig?

1. Faire Vergleiche: Jetzt können Sie wirklich sagen: „Ohne Impfung wäre Person X krank geworden. Mit Impfung ist sie es nicht." Das ist eine echte kausale Aussage.
2. Bessere Statistik: Da die Zufallszahlen jetzt perfekt übereinstimmen, sind die Berechnungen viel genauer und schneller (weniger „Rauschen").
3. Wissenschaftliche Ehrlichkeit: Es zwingt die Forscher, genau zu definieren, was ein „Ereignis" ist. Ist es der Kontakt zwischen zwei Menschen? Oder ist es die Person selbst? Die Methode macht diese Entscheidung sichtbar und kontrollierbar, statt sie dem Zufall des Computer-Codes zu überlassen.

Zusammenfassung in einem Satz

Die alten Computerprogramme vergaßen, was sie gerade berechneten, und zählten nur, wie oft sie schon gezählt hatten; die neue Methode gibt jedem Ereignis einen eigenen Namen, damit das Schicksal (der Zufall) immer fair und konsistent bleibt, egal wie sich die Geschichte verändert.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Realizing Common Random Numbers: Event-Keyed Hashing for Causally Valid Stochastic Models" auf Deutsch:

1. Problemstellung: Der Konflikt zwischen PRNG und Kausalität

Das Paper adressiert ein fundamentales Problem bei der Verwendung von Agenten-basierten Modellen (ABMs) für kausale Inferenz und die Schätzung von Behandlungseffekten (z. B. in der Epidemiologie).

• Hintergrund: Um kausale Effekte zu schätzen, vergleichen Forscher oft Paare von Simulationen (Gegenfaktische Szenarien: Baseline vs. Intervention). Eine Standardtechnik zur Varianzreduktion sind Common Random Numbers (CRNs), bei denen dieselben Zufallsinputs über verschiedene Szenarien hinweg geteilt werden, um die Kovarianz zu erhöhen und den Schätzfehler zu verringern.
• Der Fehler: In der Praxis werden CRNs typischerweise durch Wiederverwendung desselben Start-Samens (Seed) für einen zustandsbehafteten Pseudozufallszahlengenerator (Stateful PRNG) implementiert (z. B. Mersenne Twister).
• Das Kernproblem: Stateful PRNGs arbeiten sequenziell: Jeder Zufallszug verändert den internen Zustand des Generators. Wenn eine Intervention (z. B. eine Impfung) den Ausführungspfad des Codes ändert (z. B. durch das Verhindern einer Infektion, wodurch ein nachfolgender Schritt wie die Inkubationszeit-Durchführung entfällt), verschiebt sich die Anzahl der verbrauchten Zufallszahlen.
• Folge: Ein und dasselbe modellierte Ereignis (z. B. „Agent A infiziert Agent B") erhält in den verschiedenen Szenarien unterschiedliche Zufallszahlen, nicht weil sich die Mechanik geändert hat, sondern weil sich der Zugriffsindex verschoben hat. Dies verletzt die Annahme, dass die exogenen Rauschtermen ($U$) über Szenarien hinweg stabil bleiben müssen, um gültige Gegenfaktische Vergleiche zu ermöglichen.

2. Methodischer Rahmen: Strukturelle Kausale Modelle (SCMs)

Die Autoren formalisieren das Problem durch die Linse von Strukturellen Kausalen Modellen (SCMs) nach Pearl:

• SCM-Definition: Ein SCM besteht aus exogenen Variablen ($U$, das Rauschen), endogenen Variablen ($V$, der Modellzustand) und strukturellen Gleichungen ($F$).
• Interventionen: Eine Intervention ($do(X=x)$) ändert die strukturellen Gleichungen oder Eingaben, hält aber die exogenen Rauschtermen $U$ konstant.
• Die Diskrepanz:
  • Wissenschaftliches SCM: Das Rauschen $U_e$ für ein Ereignis $e$ ist eine feste Eigenschaft des Ereignisses.
  • Programmierte SCM (durch Stateful PRNG): Das Rauschen wird durch den Zugriffsindex bestimmt, der von der vorherigen Ausführungsgeschichte abhängt.
• Verletzung der Ausführungsinvarianz: Die Autoren definieren Execution Invariance als die Eigenschaft, dass die Abbildung von Ereignisidentität zu exogenem Rauschen über verschiedene Szenarien hinweg invariant gegenüber Änderungen im Ausführungspfad sein muss. Stateful PRNGs verletzen dies systematisch, da sie das Rauschen an den Zugriffsindex und nicht an die Ereignisidentität binden.

3. Lösungsmethode: Event-Keyed Random Number Generation

Als Lösung schlagen die Autoren die Kombination aus Counter-Based Random Number Generators (CBRNGs) (z. B. Philox, Threefry) und Ereignis-Identifikatoren (Event Keys) vor.

• Funktionsweise von CBRNGs: Im Gegensatz zu zustandsbehafteten Generatoren sind CBRNGs rein funktionale Algorithmen. Sie haben keinen veränderlichen internen Zustand. Die Ausgabe ist eine deterministische Funktion von Eingaben: $R = g(\text{Seed}, \text{Counter})$.
• Event-Keying: Anstelle eines sequenziellen Zählers wird als „Counter" ein eindeutiger, stabiler Ereignis-Identifikator verwendet (z. B. Hash("infection", agent_id, time)).
• Vorteil: Da die Zufallszahl nun eine explizite Funktion der Ereignisidentität ist, bleibt sie über verschiedene Szenarien hinweg identisch, solange das Ereignis selbst (z. B. der Kontakt zwischen Agent A und B) stattfindet. Änderungen im Ausführungspfad (z. B. das Auslassen eines Schritts bei anderen Agenten) beeinflussen die Zufallszahl für dieses spezifische Ereignis nicht.

4. Wichtige Beiträge und Ergebnisse

1. Formalisierung des kausalen Fehlers: Das Paper zeigt mathematisch, dass die Verwendung von Stateful PRNGs zu einer künstlichen kausalen Struktur führt. Es entstehen spuriose Pfade (z. B. führt der Infektionsstatus von Agent 1 über den Zugriffsindex zum Infektionsrisiko von Agent 2), die im wissenschaftlichen Modell nicht existieren. Dies macht individuelle Behandlungseffekte (ITEs) undefiniert.
2. Konzept der Ausführungsinvarianz: Die Einführung dieses Konzepts als notwendige Bedingung für kausal valide ABMs. Es wird argumentiert, dass dies nicht nur eine Optimierung für die Varianzreduktion ist, sondern eine fundamentale Anforderung an die kausale Kohärenz.
3. Design-Richtlinien für Event-Keys:
   • Granularität: Keys müssen fein genug sein, um unabhängige Ereignisse zu trennen.
   • Isolation: Keys dürfen keine endogenen Zustände enthalten, die sich durch Interventionen ändern (sonst wird das Rauschen wieder pfadabhängig).
   • Transworld-Identität: Die Wahl des Keys ist eine substantielle Modellierungsentscheidung (z. B. ist das Rauschen an den Kontaktslot oder an das spezifische Paar gebunden?). Diese Entscheidung muss explizit vom Forscher getroffen werden, statt implizit durch den Code bestimmt zu werden.
4. Praktische Machbarkeit: Moderne CBRNGs (wie Philox/Threefry) sind in der Geschwindigkeit mit Stateful PRNGs vergleichbar (teilweise sogar schneller in parallelen Umgebungen) und ermöglichen die notwendige Random-Access-Semantik.

5. Signifikanz und Implikationen

• Kausale Validität: Ohne Event-Keying sind individuelle Gegenfaktische Vergleiche in ABMs oft wissenschaftlich ungültig, da sie unterschiedliche Zufallsereignisse vergleichen, anstatt denselben Agenten unter verschiedenen Bedingungen.
• Statistische Effizienz: Die Varianzreduktion durch CRNs ist bei Stateful PRNGs unvorhersehbar und kann in Extremfällen sogar negativ sein (erhöhte Varianz), wenn die Rauschtermen nicht mehr korrelieren.
• Paralleles Rechnen: CBRNGs sind nativ parallelisierbar, was sie für moderne Hochleistungsrechnen-Umgebungen ideal macht, während Stateful PRNGs oft sequenzielle Abhängigkeiten erzwingen.
• Paradigmenwechsel: Das Paper fordert die ABM-Community auf, Zufallszahlengenerierung nicht als bloßen Implementierungsdetail, sondern als integralen Bestandteil des kausalen Modells zu betrachten. Die explizite Definition von Ereignis-Identitäten (Event Keys) macht die Annahmen über „transworld identity" (Identität über Welten hinweg) überprüfbar und transparent.

Zusammenfassend stellt das Paper fest, dass die Standardpraxis der Verwendung von Seed-basierten Stateful PRNGs in ABMs zu kausal inkonsistenten Ergebnissen führt. Die vorgeschlagene Methode des Event-Keyed Hashing mit Counter-Based Generators stellt die notwendige Stabilität der exogenen Rauschtermen wieder her und ermöglicht so valide kausale Inferenz auf individueller Ebene.