Random Number Generation

From Teachwiki
Jump to: navigation, search

Abstrakt[edit]

Diese Arbeit befasst sich mit den Grundmodellen(methoden) für die Generierung von Zufallszahlen. Nach einer Einführung mit Definitionen und Gebrauch der Zufallszahlen wird ausführlicher der Linear Kongruenz Generator vorgestellt. Seine Nachteile werden gezeigt und mit Beispielen veranschaulicht. Erweiterungen dieses Generators werden aufgezeigt und alternative Modelle von Generatoren von Zufallszahlen werden beschrieben.

Einführung[edit]

Gebrauch[edit]

Heutzutage spielen die Generatoren von Zufallszahlen eine wichtige Rolle in allen wissenschaftlichen Bereichen. Die zufällig generierten Zahlen haben zahlreiche Anwendungsmöglichkeiten:

  • Bei den Simulationen von verschiedenen Prozessen wie Naturphänomene, Atomkernzerfall, Zufallsmutationen(in der Biologie). Auf diese Weise untersucht man Prozesse, die nicht vorhersagbar sind und(oder) ein Teil von einem instabilen dynamischen System sind;
  • Bei numerischen Analysen und komplexen Berechnungen, wie z.B. bei der Integralrechnung im mehrdimensionalen Fall;
  • Beim Treffen von Entscheidungen: diese Methode wird oft in der Wirtschaftswissenschaft benutzt, z.B. wenn Entscheidungen über die Unternehmensstrategie getroffen werden sollen. Bei diesem Verfahren wird eine potenzielle Entwicklung auf Grund der Unternehmensstruktur simuliert und die Ergebnisse werden untersucht(analysiert). Auf Basis der Simulationsresultate wird die Unternehmenspolitik(bzw. -struktur) der Gegenwart angepasst und optimiert.

Definition[edit]

Trotz der Meinung, dass in der Mathematik oder in der Statistik eine einheitliche Definition für Zufallszahlen existieren soll, kann man keine traditionelle Definition finden. Die verschiedene Autoren und Wissenschaftler geben unterschiedliche Erklärungen, was Zufallszahlen sind und was für Eigenschaften sie besitzen. Die folgenden Eigenschaften wurden bisher in der Literatur oft beschrieben:

  • Unabhängigkeit: Die Zahlen einer Zufallsreihe sind unabhängig von einander und das Auftreten von einer Zahl beeinflusst nicht das Auftreten einer anderen Zahl.(Der Wert von Zahl a beeinflusst nicht den Wert von Zahl b). Das ist die Bedeutung von einem Korrelationskoeffizient gleich Null(Es muss nicht immer erfüllt sein. Es ist ausreichend, wenn der Korrelationskoeffizient gegen Null geht.)
  • Gleichverteilt: Diese Eigenschaft ergibt sich aus der gleichen Auftrittswahrscheinlichkeit aller Elemente der Zufallsreihe, daraus folgt, dass die Zahlen einer solchen Reihe in einem bestimmten Intervall gleich verteilt sind.

Verschiedene Typen von Generatoren von Zufallszahlen[edit]

Die Generatoren von Zufallszahlen können nach verschiedenen Kriterien gruppiert und untersucht werden. Man kann die Generatoren nach deterministischen und nichtdeterministischen Generatoren oder nach Geräten und Software Routinen unterteilen:

  • Deterministisch vs. Nichtdeterministisch Generatoren: Die deterministischen Generatoren haben die Möglichkeit, eine schon generierte Folge von Zufallszahlen mehrmals unter denselben Ausgangsbedingungen zu reproduzieren. Die nicht deterministischen Generatoren dagegen haben diese Möglichkeit nicht und sie generieren Folgen von Zufallszahlen, die einzigartig und nicht wiederholbar(zweimal reproduzierbar)sind.
  • Geräte vs. Software Routine:
    • Die Geräte, die Zufallszahlen generieren, können in zwei Gruppen unterteilt werden. Die erste Gruppe besteht aus Generatoren, die auf wirkliche physikalische Prozesse basieren. Solche Prozesse sind nicht vorhersehbar oder vorher berechenbar wie z.B Atomkernzerfall. Diese Klasse von Generatoren ist immer nicht deterministisch. Die andere Gruppe sind auch Hardware-Generatoren, die aber deterministisch sind. Sie sind nicht durch externe Prozesse gesteuert und sie werden mit der Hilfe von besonderen Bausteinen (Kondensatoren, ROM u.a.) aufgebaut. So ein Generator ist das Schieberegister mit Rückkopplung, der später in der Arbeit beschrieben wird.
    • Die Software-Routinen sind Implementierungen von Algorithmen in einer bestimmten Programmiersprache. Sie sind leicht berechenbar, wenn der Algorithmus bekannt ist. Solche Generatoren wurden Pseudogeneratoren genannt, weil die Zahlen nur zufällig aussehen. In dieser Arbeit wird auf den Begriff Pseudo aus Vereinfachungsgründen verzichten, da nur solche Generatoren tiefer betrachten werden.

Weit verbreiteter sind die Software-Generatoren, da sie den Vorteil gegenüber den hardwaretechnisch umgesetzten Generatoren haben, dass sie leicht umsetzbar und kostengünstiger sind. Aus diesem Grund konzentriert sich die Arbeit auf diese Art von Generatoren von Zufallszahlen.

Kriterien für einen guten Generator von Zufallszahlen[edit]

Bevor die verschiedenen Generatoren von Zufallszahlen dargestellt werden, müssen einheitliche Kriterien für einen guten Generator definiert werden. Folgenden Kriterien, definiert von Pierre L'Ecuyer, werden auch in dieser Arbeit benutzt:

  • Effizienz: Der Generator muss schnell und platzsparend arbeiten;
  • Reproduktion: Der Generator muss in der Lage sein, eine schon generierte Folge von Zufallszahlen mehrmals zu bilden;
  • Umgebungsunabhängigkeit: Der Generator muss unter verschiedenen Software- und Hardware-Umgebungen gleich gut funktionieren.

Es existieren weitere Eigenschaften, nach denen die Performance von einem Generator geschätzt werden kann. Diese Eigenschaften werden im Laufe dieser Thesis, bei der Darstellung von Generatoren betrachtet.

Linear Kongruenz Generator (LKG)[edit]

Wie D. Knuth schrieb, existieren viele Generatoren von Zufallszahlen. In dieser Arbeit wird der Linear Kongruenz Generator aus den folgenden Gründen ausführlich dargestellt und als Ausgangspunkt für die weitere Analyse benutzt. Der Generator spielt die Rolle eines Basismodells für die anderen in der Praxis und in der Wissenschaft meist verbreiteten Generatoren. Hinter den neu entwickelten Generatoren von Zufallszahlen steckt dieselbe Idee wie bei dem LKG. Die heutigen Generatoren haben dieselbe Struktur, nur mit verschiedenen Anfangsbedingungen, oder sie sind komplexe Kombination von Linear Kongruenz Generatoren. Obwohl die Eigenschaften des LKG nicht ideal sind, wird der Generator oft benutzt, weil er leicht zu verstehen und zu implementieren ist.

Der Linear Kongruenz Generator wurde von D.H.Lehmer im Jahre 1948 (aus anderen Quellen 1949) entwickelt und seit dem wurde er in verschiedenen Programmen und Programmiersprachen implementiert.

Funktionsweise[edit]

Der Linear Kongruenz Generator bildet eine Reihe von Integer Werten aus dem Bereich  0 \, bis m-1 \, nach der folgenden Formel:

X_{n}=(a X_{n-1} +c) mod ~ m \,

Jedes Element in der Formel hat seine wichtige Eigenschaften und Funktionen:

  •  a \, ist definiert als Multiplikator;
  •  c \, ist der Inkrement( Im Fall c=0 \, heißt dieser Generator Multiplikativ Kongruenz Generator);
  •  x_0 \, ist der Anfangswert;
  •  mod \, steht für die Modulo Operation( Division mit Rest);
  •  m \, ist das Argument der Modulo-Funktion.

Beispiel[edit]

Nehmen wir an,  a=c=x_{0}=7, m=10 \,. Das Einsetzen der Zahl 7 in die schon bekannte Formel X_{n}=(a X_{n-1} +c) mod ~ m \, gibt uns die Reihe 769076907690...\,

X_{1}=(7* 7 +7) mod ~ 10 =6 \,

X_{2}=(7* 6 +7) mod ~ 10 =9 \,

X_{3}=(7* 9 +7) mod ~ 10 =0\,

X_{4}=(7* 0 +7) mod ~ 10 =7\,

Nachteile der LKG[edit]

  • Wie das Beispiel zeigt, wiederholen sich die Pseudozufallszahlen ab einem gewissen Punkt, d.h. die generierten Folgen von Zufallszahlen geraten in einen sich wiederholenden Zyklus, oder anders ausgedrückt die Folgen haben Periode. Die Periode kann definiert werden als der kleinste Integer Wert i\,, für den das i\,-te Element gleich x_{0}\, ist. Aus der Modulo-Funktion ergibt sich, dass die Periode der Zufallsreihe nicht länger als m\, sein kann.
  • Der zweite Nachteil von dem LKG ist, dass die aufeinander folgenden Paare von Zufallszahlen mit einander korrelieren. Wenn man sich ein zweidimensionalen Raum und die Paare (x_{0}, x_{1}), (x_{1},x_{2}), (x_{2}, x_{3}),...\, vorstellt (wobei x_{i}\, das i-te Element aus der Zufallsreihe ist), verteilen sich diese Paare in dem ganzen zweidimensionalen Raum nicht gleich, sondern ordnen sie sich in Hyperebenen.

Ein sehr gutes Beispiel für diesen Nachteil ist der RANDU Generator, der auf IBM Großrechner weit verbreitet geworden ist. Bei dieser Routine ist a_{0}=65539\, und  m=2^{31}\,. Die Punkte, gebildet aus drei nacheinander folgenden Zufallszahlen, liegen in fünfzehn Hyperebenen in einem dreidimensionalen Raum. Das Bild unten zeigt diese Relation zwischen den Zahlen.

RANDU
  • Der dritte Nachteil von dem LKG wird durch ein Beispiel aus 4. Kapitel des Buches „Handbook on Simulation“ veranschaulicht. In dieser Arbeit untersucht P. L'Ecuyer die Periode von den letzten signifikanten Stellen der Zufallszahlen, wenn sie in binärer Form dargestellt werden. Die ersten acht Zahlen, die nach der folgenden Formel X_{n}=(10205 X_{n-1} +0) mod ~ 2^{15} \, generiert werden, sind 12345, 20533, 20673, 7581, 31625, 1093, 12945, 15917 und entsprechend in binärer Form:

X_{0}=12345=011000000111001_2 \,

X_{1}=20533=101000000110101_2 \,

X_{2}=20673=101000011000001_2 \,

X_{3}=~7581=001110110011101_2 \,

X_{4}=31625=111101110001001_2 \,

X_{5}=~1093=000010001000101_2 \,

X_{6}=12945=011001010010001_2 \,

X_{7}=15917=011111000101101_2 \,

P. L'Ecuyer ist zu dem Ergebnis gekommen, dass die letzten 2 Bits immer dieselben sind, das drittletzte Bit eine Periodenlänge von 2, das viert letzte – Periodenlänge von 4 usw. In seiner Arbeit macht er die Zusammenfassung, dass die letzten signifikanten Stellen weniger zufällig sind als die ersten Bits.

Basisanforderungen an der Generatorkomponenten[edit]

Der Einfluss aller diesen Nachteile kann verringert werden, wobei die Ausgangskomponenten (x_{0}, a , m,  c)\, sorgfältig ausgewählt werden. In seinem Buch erklärt D.Knuth die notwendigen Anforderungen an a , c\, und  m \, und beweist diese mathematisch. in dieser Arbiet werden die folgenden Anforderungen aufgezählt, ohne dass die Beweise hinzugefügt werden:

  • c \,und m \, müssen teilerfremd sein;
  • (a-1)\, muss ein Vielfaches von p \, sein, für jede Primzahl p \,, die m \, dividiert;
  • (a-1)\, muss ein Vielfaches von 4 sein, falls m \, Vielfaches von 4 ist.

Die wichtigste Bedingung für ein gut funktionierenden Generator bleibt die Periodenlänge. Sie hängt am stärksten von der Auswahl von m \, ab. Die meist verbreiteten Auswahlverfahren von m \, bei der Konstruktion(Implementierung) von einem LKG sind zwei:

  • Die erste Möglichkeit ist, wenn m \, gleich die größte im Rechner darstellbare Primzahl gewählt wird. Dann konstruiert man einen LKG mit Periodenlängen p=m-1\,. Aber man muss aufpassen, da jede Zufallszahl x \leq m-1 \, sein kann und kann der Fall eintreten, dass das Produkt a*x \, nicht mehr als ordinär Integer Wert darstellbar ist. Die Struktur des Generators wird auf diese Weise verändert.
  • Die zweite Möglichkeit ist, wenn m\, Potenz von 2 ist. So eine Auswahl von m \, hat den Vorteil, dass die Operation mod\, leichter berechnet wird, aber der Nachteil ist, dass die Periodenlänge stark verkürzt wird.

Das folgende Beispiel aus "Handbook on Simulation" (leicht verändert) vergleicht die Periodenlängen, ausgerechnet in beiden Fällen, 1. wenn m \, die größte Primzahl ist und 2.wenn m \, gleich Potenz von 2 ist.

1. Nehmen wir an m=2^{31}-1 \,. Das ist eine Mersennesche Primzahl, die im Jahre 1772 entdeckt wurde. Dann ist die Periodenlänge p \leq m-1 \, oder p\leq 2^{31}-1-1= 2^{31}-2\,

2. Im Fall 2 ist m=2^{31} \,(Potenz von 2) und die Periodenlänge ist p=2^{e-1}\,, wobei e die Potenz ist. d.h. p=2^{31-1}=2^{30}\,. Ergebnis: Im ersten Fall ist die Periodenlänge größer als im zweiten und die Behauptung, dass die Periodenlänge größer ist, wenn m \, gleich eine Primzahl ist, wird bestätigt.

Alternative Generatoren[edit]

Wie schon gezeigt wurde, hat der LKG viele Nachteile und er ist ganz weit entfernt von einem idealen Generator von Zufallszahlen. Viele Wissenschaftler untersuchen die Zufallszahlgeneration, um neue alternative Routinen zu entwickeln oder die alten zu optimieren. Das Ziel ist, dass die Eigenschaften von den Generatoren erweitert und verbessert werden, wobei die Nachteile abgeschwächt werden.

  • So ein Generator ist der Multiplikative Rekursive Generator (MRG), der durch die folgende Formel definiert wird:

X_{n}=(a_{1}* x_{n-1}+...+a_{k}* x_{n-k}) mod ~ m\,

In diesem Fall sind m\, und  k\, positive Integer Werte und a\, ist aus dem Intervall [-(m-1),(m-1)]\,.  k\, steht für die Anzahl der Vorgänger, die für die Berechnung einer neuen Zufallszahl benötigt werden. In diesem Fall verlängert sich die Periodenlänge auf p=m^k-1\,. Es wird die Idee entwickelt, bei der nur zwei Koeffizienten a\, ungleich Null gewählt werden d.h. eine Formel der Art:

X_{n}=(a_{r}* x_{n-r}+a_{k}* x_{n-k}) mod ~ m\,

Diese Idee ist sehr populär, da die Implementierung sehr leicht ist und der Generator sehr schnell arbeitet. Der Nachteil ist die verschlechterte Struktur der generierten Zufallszahlen.


  • Eine andere Art von Generatoren von Zufallszahlen sind die kombinierten Generatoren. Diese Generatoren generieren die Zahlen nach der folgender Formel:z_{n}=\sum(\delta_{j}*x_{j,n}) mod ~ m\,, wobei \delta_{j}\, ein Gewichtsfaktor ist und x_{j,n}\, selbst eine Zufallszahl ist, die mit der Hilfe eines anderen Generators gebildet wird. Der Vorteil von diesem kombinierten Generator, ist die verlängerte Periode der Zufallszahlenreihe und die verbesserte Struktur der generierten Folge.


  • Eine dritte Art von Generatoren sind diese, die zufällig Nullen und Einsen generieren. Hiermit werden zwei solche dargestellt. Die Idee der beiden ist ähnlich und bei gleichen Anfangsbedingungen generieren sie dieselben Zufallsfolgen. Der Unterschied ist in der Konstruktion.
    • Der erste Generator heißt Tausworthe Generator. Er bildet eine binäre Zufallsfolge von Nullen und Einsen nach der Formel: b_{i}=(a_{p}*b_{i-p}+a_{p-1}*b_{i-p+1}+...+a_{1}*b_{i-1}) mod ~ 2\,, wobei die Anfangszahlen  b_{i} \, den Wert 0 oder 1 haben.
    • Der zweite Generator ist das Schieberegister mit Rückkopplung. Er kann am besten mit einem Bild vorgestellt.
Schieberegister mit Rückkopplung

Dieser Generator unterscheidet sich von dem Ersten, weil er nicht mehr softwaretechnisch implementiert wird, sondern hardwaretechnisch mit der Hilfe von kleinen Bausteinen und Registern, wie z.B. den XOR-Bausteinen. Die Funktionsweise von dem Schieberegister kann mathematisch auf folgende Weise ausgedrückt werden: x_{n}=a_{p}\and b_{i-p} \oplus a_{p-1}\and b_{i-p+1} \oplus ... \oplus a_{1}\and b_{i-1}\,, wobei \oplus das exklusives OR ist.

Beide vorgestellte Generatoren werden immer dieselben Zufallsfolgen generieren, es sei denn die Anfangszahlen unterscheiden sich. Zum Nutzen einer bestimmten Untersuchung können die generierten binären Folgen in Teilblöcken aufgeteilt und in dezimale Zahlen umgerechnet werden. Das folgende einfaches Beispiel (Teil von dem Beispiel ist von der Thesis Random Number Generation WS05/06) wird diese Behauptung veranschaulichen. Nehmen wir an, unsere Anfangsbitfolge ist:1,0,1,0\,. Die Formel des Tausworthe Generators lautet b_{i}=(b_{i-4}+b_{i-1}) mod ~ 2\, und die entsprechende Formel des Schieberegisters ist dann x_{n}=b_{i-4} \oplus b_{i-1} \,. Wenn man die einzelnen Bits berechnet, bekommt man die generierte Bitfolge:110010001110101\,, die gleich für den beiden Generatoren ist.

Test auf Zufälligkeit[edit]

Ein ganz wichtiger Punkt bei der Generation von Zufallszahlen ist die Frage, ob die generierten Zahlen wirklich zufällig sind. Die Wissenschaftler haben verschiedene Tests entwickelt, damit sie die Zufälligkeit von den produzierten Zufallsfolgen untersuchen und deren Verteilungen analysieren können. Diese Testverfahren können wir nach empirischen und statistischen Tests unterteilen. In dieser Arbeit werden 4 empirische Tests dargestellt:

  • Frequency Test”- Bei ihm wird das Vorkommen von jeder Zahl gezählt und überprüft, ob die Zahlen gleich oft auftreten;
  • Serial Test“- Man überprüft, ob bestimmte Paare von Zahlen gleich oft vorkommen;
  • Poker Test“- Bei diesem Test bestimmt man n\,Gruppen von aufeinander folgenden Elementen und vergleicht diese mit dem bekannten Poker Blätter (two of a kind, three of a kind, straight, full house, usw.);
  • Gap Test“ - Hier wird der Abstand zwischen gleichen Elementen in einem Bereich der Zufallsfolge gemessen.

Bei den statistischen Tests ist das Problem komplizierter. Kein einziger Test kann als optimal definiert werden. Die Meinungen über dieses Thema sind kontrovers. Die verschiedenen Wissenschaftler favorisieren unterschiedliche Testalgorithmen. Eine allgemeine Erklärung, wie die statistischen Test arbeiten sollen, hat P. L'Ecuyer gegeben. Er schreibt in seiner Arbeit „Uniform Random Number Generators: A Review“, dass ein Test durch Teststatistik T, die eine Funktion mit endlicher Menge von Argumenten ist, definiert wird und deren Verteilung unter H_{0}\, bekannt ist oder approximiert werden kann. Der Test sucht empirische Beweise gegen H_{0}\, und wenn solche gefunden werden, wird H_{0}\, abgelehnt. Das passiert, wenn die Wahrscheinlichkeit p\,, dass T\, größer als ein bestimmtes t_{1}\, gegen 0\, oder 1\, geht, d.h. Zu klein, zu groß oder mathematisch ausgedrückt: p=P[T\geq t_{1}]\,. Das Nichtablehnen von H_{0}\,bedeutet nicht, dass H_{0}\, die richtige Hypothese ist. Es kann sein, dass beim zweiten Test die Hypothese abgelehnt wird. Man kann als zweite Möglichkeit die empirische Verteilung mit der theoretischen vergleichen und daraus die Schlussfolgerung ziehen, ob die beiden Verteilungen ähnlich sind. D. Knuth beschreibt in seinem Buch eine Zusammenstellung von Tests, die als Standard angesehen werden können, wie z.B. Chi-Quadrat oder Kolmogorov-Smirnov Test. Die Meinungen über die Effizienz dieser Tests sind gegensätzlich und auf diesem Grund werden diese hier nicht tiefer betrachtet. Die Wissenschaftler kamen zu der Erkenntnis, dass für die Untersuchung von Zufallsreihen mehr als ein Test benutzt werden soll. Mit diesem Gedanken hat George Marsaglia im Jahre 1996 eine Reihe von Tests, namens DIEHARD, vorgeschlagen, die als strenger als die klassische Tests von Knuth angesehen wird. In Mai 2006 hat P. L'Ecuyer eine andere Serie von Test entwickelt, die TestU01heißt.

Zusammenfassung[edit]

Nachdem es in dieser Arbeit grob um die Idee der Generierung von Zufallszahlen, deren Gebrauchsmöglichkeiten, Eigenschaften und Nachteile ging, kann schlussfolgert werden, dass kein optimaler Generator für Zufallszahlen existiert. Auf der Frage: „Welcher Generator benutzt werden soll, damit man gute Ergebnisse bekommt?“, kann man nicht präzise antworten. Die Auswahl eines bestimmten Generators hängt vom dessen Verwendungsziel und dem Zweck der durchgeführten Untersuchung ab. Es besteht die Möglichkeit den Generator zu wählen der dem angestrebten Zufälligkeitsniveau am besten entspricht.

Referenzen[edit]

1.Pierre L'Ecuyer (2004),"Random Number Generation", Chapter 2 of the Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, eds., Springer-Verlag, 2004, 35-70.

2.Pierre L'Ecuyer(1998),"Random Number Generation", Chapter 4 of the Handbook on Simulation, Jerry Banks Ed., Wiley, 1998, 93--137.(Introductory tutorial on RNGs). This handbook won the best book award for an engineering-related handbook for 1998, by the Association of American Publishers.

3.Pierre L'Ecuyer(1997),Uniform Random Number Generators: A Review

4.P. L'Ecuyer and R. Simard(2006), ``TestU01: A C Library for Empirical Testing of Random Number Generators, May 2006, Revised November 2006, ACM Transactions on Mathematical Software, to appear.

5.Donald Knuth,The Art of Computer Programming,Volume 2, Seminumerical Algorithms,Addison Wesley, Reading (MA) 1997, ISBN 0-201-89684-2

6.Primzahlen

7.History of randomness definitions, in Stephen Wolfram's "A New Kind of Science"

8.Numerical Recipes in C,Cambridge University Press