In der hier vorliegenden Arbeit wird nun so vorgegangen, dass zunächst im ersten Kapitel zwei Zufallsgeneratoren, der lineare Kongruenzgenerator und der Tausworthe-Generator vorgestellt werden. Im zweiten Kapitel geht es dann um analytische Gütekriterien, die durch grafische Darstellungen überprüft werden können. Da diese Beurteilungen eher qualitativer Natur sind und man nicht wirklich weiß, ab wann eine bestimmte Gleichverteilungshypothese tatsächlich abzulehnen ist, erfolgt im dritten Kapitel eine exakte Fassung der Problematik mithilfe statistischer Methoden. Hier werden tatsächlich geeignete Testgrößen mit Verwerfungsbereich der Nullhypothese angegeben.
Inhaltsverzeichnis
1 Einleitung
2 Zufallsgeneratoren
2.1 Lineare Kongruenzgeneratoren
2.2 Implementierung von linearen Kongruenzgeneratoren
2.3 Tausworthe Generatoren
2.3.1 Schieberegister-Generatoren
2.3.2 Tausworthe Generatoren auf Basis des Schieberegister-Generators
3 Analytische Gütekriterien für Zufallsgeneratoren
3.1 Einige analytische Überlegungen
3.2 d-gleichverteilte Folgen
3.3 Grafische Überprüfung
4 Statistische Gütekriterien
4.1 Anpassungstests
4.2 Spezielle Anpassungstests
4.2.1 Kolmogoroff-Smirnov-Anpassungstest
4.2.2 Durchführung für die betrachteten Generatoren
4.2.3 Chi-Quadrat-Anpassungstest
4.2.4 Durchführung für die betrachteten Generatoren
4.3 Anpassungstests auf Funktionen der Stichprobe
4.3.1 Gap-Test
4.3.2 Durchführung für die betrachteten Generatoren
4.3.3 Maximum aus d Test
4.3.4 Durchführung für die betrachteten Generatoren
4.4 Tests mit überlappenden Teilfolgen
4.4.1 Durchführung für die betrachteten Generatoren
5 Fazit
Zielsetzung und Themen
Die Arbeit untersucht die Qualität von Zufallszahlengeneratoren für stochastische Simulationen durch eine Kombination aus analytischen Methoden und statistischen Anpassungstests, um deren Zuverlässigkeit bei der Modellierung komplexer Prozesse zu bewerten.
- Mathematische Grundlagen linearer Kongruenz- und Tausworthe-Generatoren
- Analytische Gütekriterien und Konzepte der d-Gleichverteilung
- Implementierungsspezifische Herausforderungen bei Zufallsgeneratoren
- Durchführung verschiedener statistischer Anpassungstests (z.B. Kolmogoroff-Smirnov, Chi-Quadrat)
- Vergleichende Analyse und Validierung der Generatoren durch grafische und numerische Verfahren
Auszug aus dem Buch
2.1 Lineare Kongruenzgeneratoren
Definition:
Ein linearer Kongruenzgenerator der Ordnung k >= 1 mit dem Modulus M Element N besteht aus einem Rekursionsschema der folgenden Gestalt:
xn+1 := (Summe von i=0 bis k-1 von ai*xn-i + c) MOD M
für n >= k-1, mit den Startwerten x0, ..., xk-1 Element N0. Dabei heißen c Element N0 die additive Konstante und a0, ..., ak-1 Element N0 die Multiplikatoren (Kolonko 2008, S. 15).
Man sieht, dass diese Definition sehr allgemein linear in den xi eine rekursive Folge definiert. Die Ordnung dieser Rekursionsvorschrift gibt an, aus wie vielen vorangehenden Folgengliedern sich das nächste Folgenglied errechnet. Wir wollen im folgenden erst einmal lineare Kongruenzgeneratoren der Ordnung 1 studieren. Dies ist natürlich der Spezialfall der obigen Definition für k=1:
Definition:
Im folgenden sei LKG(a, c, M, x0) der Generator mit der Rekursionsvorschrift
xn+1 = (axn + c) MOD M
bezeichnet, mit Startwert x0 Element {0, ..., M-1}.
Da es sich um eine rekursive Folge mit endlicher Wertemenge handelt, ist klar, dass sich diese Folge irgendwann wiederholen muss. Wiederholt sich nämlich ein Element der Folge, wird von dort aus die gesamte Folge wiederholen. Demzufolge wird die maximale Periodenlänge bei einem linearen Kongruenzgenerator der Ordnung 1 erreicht, wenn die gesamte Wertemenge genau einmal durchlaufen wird (in beliebiger Reihenfolge). Demnach kann als maximale Periodenlänge überhaupt nur M erreicht werden. Für den Generator LKG(a, 0, M) kann man zeigen, dass für seine maximale Periodenlänge gilt:
L(a, 0, M) <= M / ggT(a, M) - 1
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Bedeutung von Zufallsgeneratoren für Monte-Carlo-Methoden und die Relevanz der statistischen Güte für Simulationen.
2 Zufallsgeneratoren: Theoretische Darstellung von linearen Kongruenzgeneratoren und Tausworthe-Generatoren inklusive ihrer Implementierung und Parameterwahl.
3 Analytische Gütekriterien für Zufallsgeneratoren: Herleitung analytischer Anforderungen an Zufallsfolgen, wie die d-Gleichverteilung, und Möglichkeiten der grafischen Überprüfung.
4 Statistische Gütekriterien: Umfassende Anwendung statistischer Tests wie dem Kolmogoroff-Smirnov-Test und Chi-Quadrat-Tests zur Validierung der erzeugten Zahlenfolgen.
5 Fazit: Zusammenfassende Bewertung der untersuchten Generatoren basierend auf den Testergebnissen und den theoretischen Vorgaben aus der Literatur.
Schlüsselwörter
Zufallsgeneratoren, Monte-Carlo-Simulation, Lineare Kongruenzgeneratoren, Tausworthe-Generatoren, d-Gleichverteilung, Anpassungstests, Kolmogoroff-Smirnov-Test, Chi-Quadrat-Test, Periodenlänge, Statistische Validierung, Stochastische Simulation, Gap-Test, Maximum aus d Test
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Analyse und statistischen Überprüfung von Zufallszahlengeneratoren, die essenziell für die Durchführung stochastischer Simulationen sind.
Welche Generatortypen werden schwerpunktmäßig behandelt?
Der Fokus liegt auf linearen Kongruenzgeneratoren sowie Tausworthe-Generatoren und deren mathematischen Eigenschaften.
Was ist das primäre Ziel der Untersuchung?
Ziel ist es, die Qualität von generierten Zufallszahlen sowohl analytisch zu begründen als auch durch statistische Testverfahren quantitativ zu verifizieren.
Welche wissenschaftliche Methode kommt zur Anwendung?
Die Arbeit nutzt einen mathematisch-theoretischen Ansatz zur Beschreibung der Generatoren, kombiniert mit verschiedenen statistischen Anpassungstests zur Validierung.
Welche Rolle spielt die Periodenlänge?
Die Periodenlänge ist entscheidend, da sie bestimmt, wie lange ein Generator Zufallszahlen liefern kann, bevor sich die Folge wiederholt und somit ihre statistische Qualität einbüßt.
Wozu werden statistische Anpassungstests verwendet?
Diese Tests dienen dazu, die Hypothese zu überprüfen, ob die vom Generator erzeugten Zahlen tatsächlich einer gewünschten Gleichverteilung entsprechen.
Warum wird der Kolmogoroff-Smirnov-Test eingesetzt?
Er dient als primäres Instrument, um zu prüfen, ob die empirische Verteilung der Zufallszahlen signifikant von einer theoretischen stetigen Verteilung abweicht.
Wie unterscheidet sich der Gap-Test von anderen Verfahren?
Der Gap-Test untersucht die Abstände zwischen bestimmten Ereignissen in der Zahlenfolge, um die Unabhängigkeit der erzeugten Zufallsvariablen zu prüfen.
- Quote paper
- Thomas Plehn (Author), 2009, Statistische und analytische Gütekriterien für Zufallsgeneratoren in stochastischen Simulationen, Munich, GRIN Verlag, https://www.grin.com/document/132069
