Pseudozufallszahlengeneratoren

Ein Pseudozufallszahlengenerator ist eine deterministische Rekursion, die aus einem Anfangs-Seed eine lange, reproduzierbare Zahlenfolge erzeugt, die unabhängige Ziehungen aus der Gleichverteilung auf dem Einheitsintervall nachahmt.

Definition

Ein Pseudozufallszahlengenerator ist ein Algorithmus, der durch einen Zustand, eine Übergangsfunktion, die den Zustand fortschreitet, und eine Ausgabefunktion definiert ist, die jeden Zustand einer Zahl zuordnet und eine periodische Sequenz erzeugt, die statistisch nicht von gleichverteilten Zufallszahlen zu unterscheiden sein soll.

Scope

Dieses Thema behandelt die Konstruktion von Gleichverteilungsgeneratoren (linear-kongruent, verzögert-Fibonacci, verallgemeinerte Feedback-Schieberegister und kombinierte Generatoren), die strukturellen Eigenschaften, die ihre Qualität bestimmen, wie Periodenlänge und Gitter- oder Äquidistributionsverhalten, sowie die empirischen und theoretischen Tests, die zu ihrer Zertifizierung verwendet werden. Kryptographisch sichere Generatoren werden nur als kontrastierendes Designziel erwähnt.

Core questions

• Welche Rekursionen ergeben lange Perioden und eine gute hochdimensionale Gleichmäßigkeit?
• Wie wird die Qualität eines Generators durch seine Gitterstruktur und Äquidistribution gemessen?
• Welche empirischen Testbatterien erkennen Abweichungen von der Zufälligkeit?
• Wie werden Generatoren gesät und kombiniert, um die Periode zu verlängern und die statistischen Eigenschaften zu verbessern?

Key concepts

• Seed und Zustand
• Periodenlänge
• Äquidistribution
• Gitterstruktur
• Spektraltest
• Kombinierte Generatoren

Key theories

Lineare Rekursionsgeneratoren

Linear-kongruente und Schieberegister-Rekursionen entwickeln einen ganzzahligen Zustand durch modulare Arithmetik; ihre Periode und die Gitterstruktur aufeinanderfolgender Ausgaben werden durch zahlentheoretische Eigenschaften des Multiplikators und Moduls bestimmt.

Äquidistribution und der Mersenne Twister

Generatoren, die auf verdrehten verallgemeinerten Feedback-Schieberegistern basieren, erreichen enorme Perioden und eine nachweisbare Äquidistribution in vielen Dimensionen, was sie zu einer weit verbreiteten Standardwahl für die statistische Simulation macht.

Clinical relevance

Der Standardgenerator in einem Statistikpaket bestimmt die Reproduzierbarkeit und Validität jeder Simulation, jedes Bootstrap- und Monte-Carlo-Ergebnisses, das er erzeugt; das Verständnis von Periode und Äquidistribution hilft Praktikern, Generatoren zu vermeiden, deren verborgene Regelmäßigkeiten hochdimensionale Simulationen verfälschen können.

History

Lehmer schlug die linear-kongruente Methode 1949 vor; spätere Analysen zeigten die Gitterfehler schlecht gewählter Parameter, was den Spektraltest, kombinierte Generatoren und letztlich langperiodische, äquidistribuierte Designs wie den Mersenne Twister im Jahr 1998 motivierte.

Key figures

• Donald Knuth
• Pierre L'Ecuyer
• Makoto Matsumoto
• Derrick Henry Lehmer

Seminal works

• knuth1997
• matsumoto1998

Frequently asked questions

Was macht einen Pseudozufallszahlengenerator besser als einen anderen?

Ein guter Generator hat eine sehr lange Periode, verteilt seine Ausgaben auch in vielen Dimensionen gleichmäßig, besteht Standard-Statistiktestbatterien und ist schnell und reproduzierbar. Schlechte Generatoren können kurze Perioden oder sichtbare Gittermuster aufweisen, die Simulationen verzerren.

Warum ist der Seed wichtig?

Der Seed legt den Startzustand fest, sodass die gesamte Sequenz dadurch bestimmt wird. Das Aufzeichnen des Seeds macht eine Simulation exakt reproduzierbar, während eine unvorsichtige Wahl der Seeds zu überlappenden oder korrelierten Strömen bei parallelen Läufen führen kann.