(1) |
Wie oben schon gesagt, sollte möglichst groß gewählt werden.
Die größte darstellbare Zahl des Rechners ist , wobei also
die Anzahl der bits in der arithmetischen Einheit ist,
einschließlich des Vorzeichenbits. Wählt man , so nutzt man
den vollen Zahlenbereich der positiven ganzen Zahlen aus. Das mathematische
Resultat der Summe
Auf normalen Taschenrechnern gibt es allerdings die Festkomma- Darstellung
ganzer Zahlen nur für die Adressierung (z.B. in Schleifen- Anweisungen).
Taschenrechner verwenden ausschließlich Gleitkomma- Darstellung. Hier
können wir die Überlauf- Arithmetik nicht anwenden. Stattdessen arbeiten
Taschenrechner aber mit doppelter Genauigkeit bei der Darstellung der
Mantisse, nämlich mit 64 bit oder 12 signifikanten Dezimalstellen.
Solange das mathematische Resultat noch ohne größere Rundungsfehler
von unserem Taschenrechner berechnet wird, können wir einfach die
Modulo- Funktion auf das Resultat anwenden. Der obige Programm-
Auschnitt wird dann ersetzt durch die Zeile
oder, falls die Modulo- Funktion als Systemroutine auf dem Rechner vorhanden ist,
einfach durch
.
Wir werden später in diesem Abschnitt
eine Reihe von weiteren Zufallszahlengeneratoren diskutieren. Zunächst
jedoch müssen wir zwei statistische Besonderheiten kennenlernen,
nämlich Histogramme und den - Test.
Histogramme
Wir hatten gelernt, daß die Dimension des Ereignisraumes bei der Simulation
von Pseudozufallszahlen durch den Parameter in der Rekursions-
Relation (1) gegeben war. sollte möglichst groß gewählt werden,
sodaß die Wahrscheinlichkeit für die Simulation einer bestimmten Zahl
außerordentlich klein ist, nämlich .
Wir können aber das Zahlenintervall bzw. in
kleinere Intervalle aufteilen, sodaß alle x mit
(2) |
Häufig werden in grafischen Darstellungen die theoretisch erwarteten Werte durch eine Kurve verbunden. Diese Kurven sind aber vom statistischen Standpunkt aus sehr problematisch, insbesondere dann, wenn die Intervall- Aufteilung grob ist. Durch die Summenbildung bzw. Integralbildung verlieren wir nämlich Informationen über die mathematische Wahrscheinlichkeitsverteilung, sodaß die theoretisch erwartete Verteilungsfunktion und die Kurve, die man durch Verbindung der Integralwerte erhält, verschieden sein können.
Eine Aufteilung in gleich große Intervalle ist eigentlich nur bei der
Gleichverteilung vernünftig. Im allgemeinen sollte die Intervall-
Aufteilung so durchgeführt werden, daß in jedem Intervall ungefähr
gleich viele Versuche enthalten sind, oder, anders ausgedrückt, daß die
Wahrscheinlichkeiten gleich sind für alle . Dieses
erreicht man mit der Intervalleinteilung
(3) |
Der - Test
Die gemessene Wahrscheinlichkeitsverteilung stimmt umso besser mit der
mathematisch erwarteten Verteilung überein, je kleiner die Abweichungen
zwischen mathematischer und gemessener Verteilung im Histogramm sind.
Diese triviale qualitative Aussage müssen wir quantitativ formulieren.
Hierzu dient der - Test. Wir schreiben die Abweichungen
(4) |
(5) | |||
(6) |
(7) |
(8) | |||
(9) |
(10) |
Diesen - Test und weitere Tests zur Prüfung von Hypothesen
werden in einem späteren Kapitel noch ausführlicher diskutiert.
Wir werden dann zeigen daß
und
gewählt werden muss. Im folgenden werden wir eine
Hypothese akzeptieren, wenn beim - Test ein - Wert mit
(11) |
Der Korrelationstest
Mit dem - Test können wir prüfen, ob die
zugrundeliegende Zahlenfolge des Zufallszahlen- Generators mit der Hypothese
einer gleichverteilten Veränderlichen verträglich ist. Dieser Test sagt
aber nichts über Korrelationen aus. So ist z.B. die Zahlenfolge (mit
und für , siehe (1)
(12) |
Im folgenden Reihen- Korrelationstest prüfen wir, ob die
Zufallszahl mit der vorher generierten Zahl
korreliert ist. Gegeben seien Zufallszahlen
(13) |
(14) |
Wir fassen zusammen: Die Unabhängigkeit aufeinanderfolgender Zahlen in einer Folge von Zufallszahlen ist dadurch definiert, daß der Reihen- Korrelationskoeffizient (13) der Bedingung (14) genügt. Dieses heißt aber nicht, daß die Zahlenfolge unabhängige Veränderliche im exakt statistischen Sinne liefert. Das Verschwinden des Korrelationskoeffizienten ist notwendig, aber nicht hinreichend. Daher nennt man diese Zufallszahlen auch Pseudo- Zufallszahlen.
In einer viel beachteten Arbeit hat Marsaglia gezeigt, daß, obwohl manche
Generatoren hervorragende Eigenschaften im Reihen- Korrelationstest zeigen,
diese total bei der Simulation von zufälligen Punkten in mehrdimensionalen
Räumen versagen. In einem - dimensionalen Raum würfelt man nacheinander die
Koordinaten auf den Achsen. Sei die Zahlenfolge
Der Phasentest
Ein weiterer Test für die serielle Unabhängigkeit
von Zufallszahlen ist der Phasentest. Gegeben sei eine Zahlenfolge
(15) |
Für eine vorgegebene Zahlenfolge kann man die Unabhängigkeit dann mit Hilfe des - Tests prüfen.
Das Testprogramm
Ein Java
Applet,
das die soeben diskutierten Tests durchführt,
können Sie hier aufrufen. Zuerst müssen Sie einen der bereits vorprogrammierten Generatoren
aufrufen. Wählen Sie dazu im Menu Generatoren zunächst den Generator JavaRandom auf.
Dieses ist der Standard- Generator der Java Programmiersprache. Den Source Code können Sie mit dem
Menu- Button Source einsehen. Es wird ein internes Fenster mit dem Listing eingeblendet.
Danach wählen Sie im Menu Plots die für Sie interessanten Histogramme auf. Das Histogramm
GleichVert zeigt die Gesamtverteilung. Die erwarteten Mittelwerte und Varianz dieser Verteilung sind.
Die weiteren wählbaren Generatoren sind der RN32, der bereits in Tabelle 1 angegeben war, sowie die Generatoren Ranmar, Ranlux und Ranecu, die wir später noch diskutieren werden. Als Beispiel eines schlechten Generators (BadRandom) haben wir in einem an sich guten 16-bit Generator einen Schreibfehler eingebaut (siehe Source Code). Dieses Beispiel zeigt, dass es offensichtlich in der Rekursionsrelation (1) auf die richtige Wahl der Parameter ankommt. Dieses wird uns im Rest dieses Kapitels beschäftigen. Nach einigen Minuten Rechenzeit haben wir die Ergebnisse in Tabelle 2 erhalten.
Theorie | JavaRandom | RN32 | Ranmar | BadRandom | |||
Gleichverteilungs- Test: | |||||||
0.500 | 0.0497 | 0.500 | 0.498 | 0.455 | |||
0.289 | 0.290 | 0.288 | 0.289 | 0.271 | |||
Chi2-Test: | |||||||
0. | 0.078 | 0.092 | 0.036 | 1.679 | |||
1. | 0.990 | 0.925 | 0.980 | 0.686 | |||
Korrelations- Test: | |||||||
-0.010 | -0.006 | -0.005 | -0.002 | 0.288 | |||
0.099 | 0.102 | 0.109 | 0.103 | 0.060 | |||
Phasen- Test: | |||||||
Übereinstimmung | gut | sehr gut | gut | schlecht |
Natürliche Zahlen
Für die folgenden Erörterungen benötigen wir noch einige Begriffe aus der
Theorie der natürlichen Zahlen. Der wohl wichtigste ist der Begriff der
Primzahl. Eine Zahl aus der Menge der natürlichen Zahlen heißt
Primzahl, wenn außer durch sich selbst und der Zahl 1 durch keine
andere natürliche Zahl ohne Rest teilbar ist. Bereits Euklid hat
300 v.Chr. festgestellt, daß es unendlich viele Primzahlen gibt. Unter
Primzahlzwillingen versteht man zwei Primzahlen, die durch genau eine
Nicht- Primzahl voneinander getrennt sind, z.B. 5 und 7 oder 17 und 19.
Ein wichtiger Satz in diesem Zusammenhang ist der folgende
Satz: Jede Zahl zwischen zwei Primzahlzwillingen ist durch 2 und 3 und damit
auch durch 6 teilbar.
Will man daher alle Primzahlzwillinge aufsuchen, muß man nur alle Vielfachen
von 6 bilden und dann die vorherige und nachfolgende Zahl auf die Eigenschaft
,,Primzahl'' prüfen. Ob es unendlich viele Primzahlzwillinge gibt, ist bis heute
nicht gezeigt worden.
Unter einer kanonischen Zerlegung einer natürlichen Zahl versteht
man eine Zerlegung in Primzahl- Potenzen
(16) |
Dividiert man eine beliebige natürliche Zahl durch eine beliebige andere
natürliche Zahl , so erhält man im allgemeinen einen Rest.
Der kleinste positive Rest ist durch die Formel
Als praktisches Beispiel bestimmen wir den größten gemeinsamen Teiler
der Zahlenfolge
. Nach Streichen der Null und
Division durch 36 ergibt der erste Schritt
Multiplikative Kongruenzmethode
Wir kommen jetzt auf die Diskussion der allgemeinen Rekursionsrelation
(1) zurück, die wir der Wichtigkeit halber noch einmal notieren:
(17) |
(18) |
(19) |
(20) |
(21) |
(22) |
Wir gehen jetzt auf den wichtigsten und gleichzeitig einfachsten Spezialfall
ein, nämlich auf die spezielle multiplikative Kongruenzmethode mit
Modul :
(23) |
Interessanter wird es jetzt bei , d.h. . Erlaubte - Werte
sind für die Zahlen 1, 3, 5, 7, 9, 11, 13 und 15. Wie der Leser
leicht nachprüfen kann, ergeben sich für die Periodenlängen
Wir kommen jetzt noch einmal auf den bereits am Anfang dieses Kapitels
diskutierten Generator
Eine Erweiterung dieses Generators ergibt sich durch Hinzunahme des
Summanden :
(24) |
Zusammenstellung der wichtigsten Kongruenzmethoden
Im folgenden geben wir eine Zusammenstellung der am häufigsten benutzten
Parameter in professionellen Anwendungen. Alle Generatoren verwenden keine
additive Konstante, d.h. .
1. , : Dieses sind die Parameter, die Lehmer [ ] in seiner
Originalarbeit über multiplikative Kongruenzmethoden vorgeschlagen hatte.
2. , : Dieses ist ein Produkt der Computerfirma IBM
für ihre /360- Serie. Die Parameter wurden optimiert, um einen möglichst
kleinen Reihen- Korrelationskoeffizienten zu erhalten. Unglücklicherweise
hat dieser Generator verheerende Korrelationen höherer Ordnung im
- dimensionalen Raum. Der Grund hierfür scheint zu sein, daß der
- Wert nicht die Relation
Fibonacci- Generatoren
Wir hatten im Rahmen der Kombinatorik bereits eine Fibonacci-
Sequenz kennengelernt:
(25) |
Die Fibonacci- Generatoren sind zwar in unzähligen Arbeiten theoretisch untersucht worden, eine klare Antwort ist jedoch (zumindest für den Autor dieses Tutorials) nicht erkennbar. Es muß jedoch schon jetzt erwähnt werden, daß der beste Generator, der gegenwärtig auf dem Markt ist, ein Fibonacci- Generator ist (siehe später).
Vergrößerung der Periodenlänge
Alle von uns bisher diskutierten Generatoren hatten eine Periodenlänge
in der Größenordnung ihres Moduls. Mit anderen Worten, nachdem ungefähr alle
Zahlen aus dem Zahlenbereich einmal generiert worden waren,
wiederholte sich die Zahlenfolge in exakt gleicher Weise. Wenn also
Man kann nun aber die Periodenlänge in einfachster Weise vergrößern, indem man in der zweiten Zahlenfolge eine Permutation der Zahlen erzeugt. Die verschiedenen Permutationen dürfen keine Korrelation zeigen, d.h. die Permutationen müssen mit einem zweiten, unabhängig vom ersten Generator laufenden, Zufallszahlen- Generator ausgewürfelt werden. Gemäß der 1. Grundaufgabe der Kombinatorik kann man dann, zumindest im Prinzip, eine Vergrößerung der Periodenlänge um den Faktor erwarten. Wir wollen in diesem Zusammenhang zwei Generatoren diskutieren, die heutzutage (2004) als das beste angegeben werden, was es auf dem Markt gibt, nämlich der Generator RANECU von L'Ecuyer [ ] und der Generator RANMAR von Marsaglia [ ]. Beide Generatoren arbeiten nicht, wie bisher alle diskutierten Generatoren, mit der Überlauf- Arithmetik. Alle Rechenoperationen bleiben im Zahlenbereich des Rechners. Es gibt Versionen für 16-bit und 32-bit Rechner. Wir diskutieren hier die 32-bit Versionen.
Der RANECU Generator
L'Ecuyer beschreibt einen Generator, der aus 2 (b.z.w. 3) multiplikativen
Kongruenzmethoden besteht, aber so, daß alle Rechenoperationen innerhalb
des Zahlenbereichs des 32-bit (b.z.w. 16-bit) Rechners bleiben. Die
Begründung dieses Generators ist nicht einfach zu verstehen.
Die Parameter in den beiden kombinierten Kongruenzen sind , und , und sollten nicht verändert werden. Man erkennt, daß keine dieser Zahlen etwas mit unseren bisherigen Kriterien für ,,gute'' Zufallszahlen- Generatoren zu tun hat. Trotzdem hat sich gezeigt, daß der Generator hervorragende Eigenschaften bezüglich der Gleichverteilung, der seriellen sowie der Unabhängigkeit höherer Ordnung besitzt. Die Periodenlänge ist .
Der RANMAR Generator
Dieser Generator von Marsaglia und Zamann basiert auf zwei
Fibonacci- Sequenzen, eine mit einer Subtraktion und Modulo- Funktion, die
andere auf einer einfachen Subtraktion. Auch in diesem Fall wollen wir nicht
die Einzelheiten diskutieren, es geht über den Rahmen dieses Tutorials hinaus.
Wichtig ist lediglich, daß die Startwerte IR und IS aus nicht mehr als
5 dezimalen Ziffern bestehen dürfen und die Relationen
Aufgaben
Aufgabe 1: Untersuchen Sie den System- Generator Ihres Rechners. Suchen Sie dazu im Source Code der Java Distribution den entscheidenden Code heraus, der beim einfache Aufruf Math.random() interpretiert wird. Welcher Algorithmus verbirgt sich hinter diesem Generator ?
Aufgabe 2:
Diskutieren Sie die Periodenlänge des Generators