Zufallszahlengenerierung

Die Zufallszahlengenerierung erzeugt Zahlenfolgen, die sich verhalten, als wären sie aus einer Zielwahrscheinlichkeitsverteilung gezogen worden, und liefert die stochastischen Eingaben, auf denen Monte-Carlo-Simulationen, Resampling und randomisierte Algorithmen basieren.

Definition

Zufallszahlengenerierung ist die Konstruktion und Analyse von Algorithmen, die Zahlen erzeugen, welche unabhängige Ziehungen aus einer spezifizierten Wahrscheinlichkeitsverteilung approximieren, ausgehend von einer gleichmäßigen Quelle auf dem Einheitsintervall.

Scope

Dieser Bereich umfasst die deterministischen Algorithmen, die gleichmäßige pseudozufällige Sequenzen erzeugen, die Transformationen, die gleichmäßige Zufallsvariablen in Stichproben aus beliebigen Verteilungen umwandeln, Akzeptanz-Ablehnungs-Verfahren für Dichten, die nicht in geschlossener Form invertiert werden können, und Varianzreduktionsmechanismen, die die Effizienz von Simulationsschätzern verbessern. Hardware-Entropiequellen und kryptographische Generatoren werden als Grenzfälle erwähnt, der Fokus liegt jedoch auf Generatoren für die statistische Simulation.

Sub-topics

• inverse transform sampling
• pseudorandom number generators
• rejection sampling
• variance reduction techniques

Core questions

• Wie kann ein deterministischer Algorithmus Sequenzen erzeugen, die statistische Tests auf Zufälligkeit und Gleichmäßigkeit bestehen?
• Wie werden bei einem gleichmäßigen Generator Stichproben aus einer beliebigen Zielverteilung gewonnen?
• Wie wird bei intrakter Inversion mittels Akzeptanz-Ablehnung aus einer Dichte gezogen?
• Wie kann die Varianz eines Simulationsschätzers reduziert werden, ohne die Stichprobengröße zu erhöhen?

Key theories

Pseudozufällige gleichmäßige Generierung

Eine Rekursion mit langer Periode und guter Gitterstruktur erzeugt deterministische Sequenzen, die statistisch nicht von unabhängigen gleichmäßigen Ziehungen zu unterscheiden sind; die Qualität wird anhand der Periodenlänge, der Äquidistribution und von Batterien empirischer Tests bewertet.

Transformationsmethoden

Die Wahrscheinlichkeitsintegraltransformation und ihre Verwandten bilden gleichmäßige Zufallsvariablen auf eine Zielverteilung ab: Die Anwendung der inversen kumulativen Verteilungsfunktion liefert exakte Stichproben, wann immer sie ausgewertet werden kann.

Akzeptanz-Ablehnungs-Stichproben

Durch Vorschläge aus einer leicht zu ziehenden Hüllkurve, die die Zieldichte dominiert, und die Annahme von Vorschlägen mit einer Wahrscheinlichkeit, die dem Dichteverhältnis entspricht, erhält man exakte Stichproben aus Dichten, die nicht invertiert werden können, zu Kosten, die durch die Enge der Hüllkurve bestimmt werden.

Clinical relevance

Eine zuverlässige Zufallszahlengenerierung ist die Grundlage für Monte-Carlo-Integration, Bootstrap- und Permutationsinferenz, Bayes'sche Posterior-Stichproben, randomisierte Experimente und Simulationsstudien in allen Wissenschaften; schlechte Generatoren mit kurzen Perioden oder Gitterartefakten können Simulationsergebnisse unbemerkt verzerren, daher ist die Qualität des Generators ein grundlegendes Anliegen für die Reproduzierbarkeit.

History

Frühe Monte-Carlo-Arbeiten in Los Alamos basierten auf einfachen kongruenten und Mittquadrat-Verfahren; die folgenden Jahrzehnte deckten deren Mängel auf und führten zu einer rigorosen Theorie der Gitterstruktur und Äquidistribution, die in Generatoren mit langer Periode und standardisierten Testsuiten zur Bewertung der Zufälligkeit mündete.

Key figures

• Luc Devroye
• Donald Knuth
• Pierre L'Ecuyer
• John von Neumann

Seminal works

• devroye1986
• knuth1997

Frequently asked questions

Sind computergenerierte Zufallszahlen wirklich zufällig?

Die meisten sind pseudozufällig: Ein deterministischer Algorithmus erzeugt eine reproduzierbare Sequenz aus einem Startwert (Seed). Gut konzipierte Generatoren haben sehr lange Perioden und bestehen statistische Tests, sodass die Ausgabe für Simulationszwecke nicht von echter Zufälligkeit zu unterscheiden ist, während sie bei festem Startwert exakt reproduzierbar bleibt.

Warum ist die inverse kumulative Verteilungsfunktion so zentral?

Wenn U gleichmäßig auf (0,1) verteilt ist, liefert die Anwendung der inversen kumulativen Verteilungsfunktion einer beliebigen Verteilung auf U eine Stichprobe aus dieser Verteilung. Diese Wahrscheinlichkeitsintegraltransformation ist exakt und die Standardmethode, wann immer die Inverse berechnet werden kann.