1 Grundlagen

1.1 Was ist Simulation?

Unter Simulation versteht man die Nachbildung eines real existierenden Sachverhalts anhand eines Modells. Dabei werden in der Realität stattfindende physikalische, technische, biologische oder ökonomische Prozesse durch mathematische Modelle nachgebildet.

1.2 Anwendungsbereiche und Zielsetzung

Durch Simulation sollen Lösungen von wirtschaftswissenschaftlichen Problemstellungen erarbeitet werden. So ist z.B. die Simulation eines Systems denkbar, bis optimale Werte erreicht sind.

Ein Beispiel für Simulation ist der Aufbau und die Funktionsweise von Transportwegen, wie zum Beispiel Autobahnen, Flughäfen oder U-Bahnen. Das Verhalten eines Systems kann durch sie aufgezeigt werden. Die Simulation stellt ein Werkzeug zur Entscheidungsfindung dar.

Eine weitere Möglichkeit stellt das Experimentieren mit einem Simulationsmodell dar. Es ist einfacher, kostengünstiger, ungefährlicher und schneller als die Untersuchung des Originals. Dabei ist wichtig, daß Erkenntnisse, die durch das Modell gewonnen werden, sich auf die Realität übertragen lassen. Das Simulationsmodell soll das Verhalten eines realen Systems im Zeitverlauf widerspiegeln.

In der Praxis lassen sich viele Sachverhalte durch statistische Verteilungen charakterisieren. Wenn man in der Lage ist, Zufallszahlen aus einer solchen Grundgesamtheit zu erzeugen, kann man den Sachverhalt anhand eines Modells simulieren.

So kann z.B. die Arbeitsgenauigkeit einer Maschine durch die Normalverteilung mit einem

bestimmten Erwartungswert und einer bestimmten Varianz simuliert werden. Eine

weitere Möglichkeit, einen real existierenden Sachverhalt durch die Normalverteilung zu simulieren ist die erwartete Lebensdauer von Gütern (z.B. Autoreifen). Wartezeiten können durch die Exponentialverteilung simuliert werden, die von dem Parameter abhängen.

Die Poissonverteilung, die ebenfalls vom Parameter abhängig ist, eignet sich z.B. zur Simulation von Unfällen an Straßenkreuzungen, bzw. zur Simulation von Versicherungsfällen einer Versicherungsgesellschaft.

1.3 Vorteile und Nachteile bei der Simulation

Um einen direkten Vergleich zu ermöglichen, werden die Vor- und Nachteile von Simulation in einer tabellarischen Darstellung gegenübergestellt:

2 Zufallszahlengeneratoren

2.1 Echte Zufallszahlengeneratoren

Bei echten Zufallszahlengeneratoren handelt es sich um mechanische oder elektrische Geräte, die Zufallszahlen aus der ihnen zugrunde liegenden Verteilung liefern. Diese Geräte wurden bereits in den 30er Jahren entwickelt.

Ein Beispiel für mechanische Zufallszahlengeneratoren sind Würfel (6-seitige, 10-seitige, 20seitige).

Ein Beispiel für einen elektrischen Zufallszahlengenerator ist der Generator ERNIE(Electronic Random Number Indicator Equipment). Die Erzeugung von Zufallszahlen basiert hier auf der Erzeugung von Geräuschimpulsen bei Neonröhren, welche innerhalb konstanter Intervalle mit Hilfe von Zähleinrichtungen in Zufallszahlen umgewandelt werden. Verwendung fand dieser Generator bei Ziehung der Gewinner der ,,premium bond savings lottery" in Großbritannien.

Der Vorteil von ,,echten" Zufallszahlengeneratoren ist, daß eine Prognose wie ein Zufallsexperiment ausgehen wird, nicht möglich ist.

Soll allerdings ein Zufallsexperiment mit genau den gleichen Zufallszahlen ein zweites Mal durchgeführt werden so ist dies nicht möglich. Ein Grund für ein solches Vorgehen ist z.B. die Veränderung von Parametern der zugrunde liegenden Verteilung, um Veränderungen im Simulationsablauf vorher und nachher festzustellen.

Ein weiterer Nachteil, der bei echten Zufallszahlengeneratoren auftreten kann, ist der, daß sich die zugrunde gelegte Verteilung aufgrund von Verschleiß der mechanischen Generatoren schleichend verändert. ,,Echte" Zufallszahlengeneratoren müssen daher immer daraufhin überprüft werden, ob die Zufallszahlen, die sie liefern immer noch der Verteilung entsprechen, die zugrunde gelegt ist.

2.2 Pseudozufallszahlengeneratoren

Bei Pseudozufallszahlen handelt es sich um ,,Zufallszahlen" die mit Hilfe eines mathematischen Algorithmus erzeugt werden. Streng genommen sind diese Zahlen nicht zufällig, denn mit Kenntnis des erzeugenden Algorithmus ist jede Person in der Lage, genau die gleiche Folge von Zufallszahlen zu reproduzieren, beziehungsweise die nachfolgenden ,,Zufallszahlen" vorauszusagen.

Vorteil der Pseudozufallszahlengeneratoren ist, daß verschiedene Experimente mit den gleichen Zufallszahlen durchgeführt werden können, bei gleichzeitiger Änderung der zugrunde liegenden Parameter. Die Simulationsergebnisse lassen sich so miteinander vergleichen.

Der große Nachteil der Pseudozufallszahlengeneratoren ist jedoch, daß durch Kenntnis des Algorithmus erzeugte Zufallszahlen nicht mehr zufällig, sondern berechenbar sind.

3  Erzeugung von Zufallszahlen  

3.1  Gleichverteilte Zufallszahlen  

3.1.1  Erzeugung von gleichverteilten Zufallszahlen durch echte Zufallszahlengeneratoren  

3.1.1.  a) Generierung von Zufallszahlen im Intervall 0,15  

  Durch folgenden echten Zufallszahlengenerator können Zahlen im Intervall 0,15 generiert  

  werden:  

1.  4 faire Münzen werden einmal geworfen  

2.  das Ergebnis wird notiert, wobei Kopf dem Wert 0 und Zahl dem Wert 1 entspricht  

3.  jede Münze wird einer Variablen zugeordnet  

4.  durch folgenden Algorithmus wird die Zufallszahl errechnet:  

  Folgende Realisationen sind möglich:  

  daraus  

  Ergebnis resultierende  

  Zahl  

   0

   8

   4

   2

   1

   12

   10

   9

   6

   5

   3

   14

   13

Da dieser Algorithmus Zufallszahlen aus dem Intervall [0,15] liefert, gleichverteilte Zufallszahlen jedoch häufig nur aus dem Intervall [0,9] benötigt werden, werden 3/8 der so erzeugten Zahlen verworfen. Dieser Algorithmus ist also sehr ineffizient.

3.1.1.b) Generierung von Zufallszahlen in dem Intervall [0,999]

Eine weitere Möglichkeit, gleichverteilte Zufallszahlen zu erzeugen, stellt die Entnahme von Telefonnummern aus einem Telefonbuch dar. Es wird eine Telefonnummer herausgegriffen, anschließend werden die ersten Ziffern, bis auf die letzten drei abgeschnitten. Zufallszahlen, aus dem Intervall [0,999] sind so möglich.

3.1.1.c) Problem bei der Generierung von Zufallszahlen

Zufallszahlen, die durch ,,echte" Zufallszahlengeneratoren erzeugt werden, müssen ständig

darauf überprüft werden, ob sie tatsächlich Zufallszahlen aus der Verteilung liefern, die angenommen wird. Sonst kann es dazu kommen, daß Verzerrungen (z.B. durch Abnutzung der Würfel o.ä.) bei der Zufallszahlengenerierung auftreten.

Wurf einer Münze: aufgrund einer Verzerrung

Wurf eines Würfels:

3.1.2 Erzeugung von gleichverteilten Zufallszahlen durch Pseudozufallszahlengeneratoren Pseudozufallszahlen werden durch einen mathematische Algorithmen erzeugt, wie nachfolgend aufgeführt:

3.1.2.a) Pseudozufallszahlengeneratoren

Ein einfacher Algorithmus für die Erzeugung von Zufallszahlen aus dem Intervall [0,1[ ist folgender:

Restbruch von für alle

Von der erzeugten Zufallszahl wird die Vorkommastelle abgeschnitten, anschließend wird der Restbruch (d.h. die Nachkommastellen) auf die dritte Stelle gerundet.

Für ist der Startwert 0.5 gewählt worden.

Folgende Zufallszahlen sind mit dem Algorithmus erzeugt worden, die Tabelle ist dabei von links nach rechts zeilenweise zu lesen:

3.1.2.b) Kongruenzgeneratoren

Eine weitere Alternative zur Erzeugung von Zufallszahlen stellen die Kongruenzgeneratoren dar. Sie werden durch die nachfolgende Rechenvorschrift erzeugt:

(mod ) für

Die Parameter und sind vor Erzeugung von Zufallszahlen vorgegeben. Sie stellen während der Simulation Konstanten dar. Der Parameter ist der Multiplikator, stellt das

Inkrement dar. Der Parameter ist der Modulus. ist der Startwert. Er wird zu Beginn der

. Wird der Algorithmus mit genutzt, spricht man von einem multiplikativen Generator, ist spricht man von einem gemischten Generator. Die maximale Anzahl von verschiedenen Zufallszahlen kann nur bei den gemischten Generatoren erreicht werden.

Die Problematik, die bei dieser Art von Zufallszahlengenerierung auftritt ist die ,,richtige"

Wahl der Parameter und . Sie sind so zu wählen, daß eine möglichst große

Zykluslänge, d.h. möglichst viele verschiedene Realisationen innerhalb von auftreten.

Um die maximale Zykluslänge zu erreichen, sind nach Morgan [S.58] folgende Restriktionen bei der Wahl der Parameter zu beachten: 1.) und dürfen keine Faktoren außer 1 gemeinsam haben

2.) ist ein Vielfaches jeder Primzahl, die dividiert 3.) ist ein Vielfaches von 4, wenn ein Vielfaches von 4 ist

Beispiel für einen Kongruenzgenerator mit maximaler Zykluslänge:

Beispiel für , :

Wie man leicht nachprüfen kann, sind die 3 Restriktionen nach Morgan erfüllt:

Zu 1.) Primfaktorzerlegung von und :

und enthalten keine gemeinsamen Faktoren außer 1.

Zu 2.)

Die einzige Primzahl, die dividiert ist die 2, 4 ist ein Vielfaches von 2.

Zu 3.)

à Vielfaches von 4 ist ein Vielfaches von 4,

Weitere Besonderheiten:

Wird der Multiplikator . gesetzt, so ergibt sich die konstante Zahlenfolge

: Beispiel für

Wird der Multiplikator gesetzt, so ergibt sich die offensichtlich nicht zufällige

Zahlenfolge (mod ):

Beispiel für :

Für die Generierung von gleichverteilten Zufallszahlen ergänzt man die Formel wie folgt:

. Realisationen aus dem Intervall [0,1] sind nun möglich.

Ein Problem, welches bei Kongruenzgeneratoren auftreten kann, ist die Abhängigkeit der erzeugten Zufallszahlen voneinander.

Erzeugt man durch die Rechenvorschrift (mod 1000) Zufallszahlen, die

anschließend durch zu -verteilten Zufallszahlen transformiert werden, und

plottet diese gegeneinander auf, so entsteht die unten aufgeführte Abbildung.

Abbildung 1: Morgan [S. 62] Plot von gegen für 500 -verteilte Zufallszahlen.

Es ist deutlich ein Muster zu erkennen. Ist nur dieses Muster bekannt, welches ein Algorithmus erzeugt, ohne das die Rechenvorschrift selbst bekannt ist, sind bereits gute Vorhersagen für die nächste Zufallszahl zu machen. Dies ist natürlich nicht gewollt. Um diesen Mangel zu beheben verwendet man folgendes Verfahren:

Die erzeugten Zufallszahlen werden in Gruppen zu jeweils Werten aufgeteilt.

Anschließend werden die Zufallszahlen vertauscht. Diese Vertauschung kann entweder von vorn herein festgelegt sein oder durch einen weiteren zufälligen Prozeß generiert werden. Ist die Erzeugung zufällig, so kann sie mittels eines zweiten Kongruenzgenerators erfolgen. Dieser erzeugt Zufallszahlen aus dem Intervall [0,99]. Die -te Zahl aus dem ersten Intervall, die der zweite Generator erzeugt, wird als Zufallszahl genommen. Sind alle Zufallszahlen aus dem ersten Intervall verbraucht, so werden die Zufallszahlen aus dem zweiten Intervall benutzt.

Nach dieser Vertauschung sieht das Plot gegen wie folgt aus:

Abbildung 2: Morgan [S. 63] Plot von gegen für 500 -verteilte

gewählt, die Vertauschung der Zahlen Zufallszahlen, es wurde die Intervallgröße

innerhalb der Intervalle wurde mit dem Algorithmus vorgenommen. Der Startwert ist 0.5.

Die Vertauschung hat zur Folge, daß innerhalb des Plots keine Muster, also keine

Gesetzmäßigkeiten mehr bestehen. Durch Kenntnis einer Zufallszahl ist es nun nicht mehr

möglich, auf die nachfolgende Zufallszahl zu schließen.

3.2 Nicht-Gleichverteilte Zufallszahlen

3.2.1 Die ,,Table-look-up-Methode"

3.2.1.a) Simulation von diskreten Verteilungen mittels der ,,Table-look-up-Methode" Nachfolgend soll die Simulation einer -verteilten Zufallsvariable erörtert werden.

Eine Münze wird 10 mal geworfen, jedes Eintreten des Ereignisses Zahl wird addiert. Folgende Realisationen des Experimentes sind möglich:

0  0.0010 0.0010  

1  0.0098 0.0107  

2  0.0439 0.0547  

3  0.1172 0.1719  

4  0.2051 0.3770  

5  0.2461 0.6230  

6  0.2051 0.8281  

7  0.1172 0.9453  

8  0.0439 0.9893  

9  0.0098 0.9990  

10  0.0010 1.0000  

  Will man nun obigen Sachverhalt durch einen mathematischen Algorithmus simulieren,  

  benötigt man zunächst eine gleichverteilte Zufallsvariable Das Intervall wird in  

  Teilintervalle aufgespalten. Die Breite der einzelnen Klassen richtet sich dabei nach der  

  Verteilungsfunktion der Binomialverteilung  

  Teilintervall Intervalllänge Anzahl Kopf  

1.  Teilintervall 0,0.0010  0

2.  Teilintervall 0.0010,0.0107  1

3.  Teilintervall 0.0107,0.0547  2

4.  Teilintervall 0.0547,0.1719  3

5.  Teilintervall 0.1719,0.3770  4

6.  Teilintervall 0.3770,0.6230  5

7.  Teilintervall 0.6230,0.8281  6

8.  Teilintervall 0.8281,0.9453  7

9.  Teilintervall 0.9453,0.9893  8

10.  Teilintervall 0.9893,0.9990  9

  11 Teilintervall 0 9990,1 0000  10

Abbildung 3:Morgan [S.92]: Illustration, nach der die ,,Table-look-up"-Methode arbeitet.

Durch verschiedene Realisationen der gleichverteilten Zufallsvariablen kann der

Ausgang der Binomialverteilung simuliert werden:

Teilintervall

0,2587 4 5mal Kopf

0,6579 6 7mal Kopf

0,8928 7 8mal Kopf

0,3517 4 5mal Kopf

allgemein:

Es liegt eine diskrete Verteilung zugrunde mit verschiedenen möglichen Realisationen

.

Die Wahrscheinlichkeit des Eintretens des Ereignisses ist für .

Die Zufallsvariable nimmt den Wert 0 an, wenn gilt:

für Die Zufallsvariable nimmt den Wert j an, wenn gilt:

Die Summe der Teilintervalle ergibt:

Aus diesem Sachverhalt kann man nun auch herleiten, aus welchem Grund die ,,Table-lookup"-Methode ihren Namen hat:

Die Realisation einer gleichverteilten Zufallsvariablen wird mit der

Verteilungsfunktion einer diskreten Zufallsvariable verglichen. Die gleichverteilte Zufallsvariable fällt dabei in ein Teilintervall, welches durch die Verteilungsfunktion der zu simulierenden, diskreten Zufallsvariablen vorgegeben wird. Je nachdem, in welches Teilintervall die gleichverteilte Zufallsvariable fällt, kann der Ausgang des Experimentes abgelesen werden.

Vorteil dieser Methode ist, daß für die Berechnung von kumulativen Wahrscheinlichkeiten Rekursionsformeln existieren. Die Klassengrenzen für die Teilintervalle können so schnell ermittelt werden.

Für den Fall der Binomialverteilung ist die Wahrscheinlichkeitsfunktion gegeben durch:

für .

Nachteil dieser Methode ist, daß jede erzeugte Zufallszahl mit der vertafelten

Verteilungsfunktion verglichen werden muß, um zu ermitteln in welches Teilintervall die gleichverteilte Zufallszahl fällt. Für Binomialverteilungen mit kleinem mag dieser Mangel nicht so sehr ins Gewicht fallen, für wachsendes wirkt er sich jedoch immer gravierender aus. Mit größer werdendem steigt die Zeit für die Berechnung der kumulierten Wahrscheinlichkeiten an.

3.2.1.b) Simulation von stetigen Verteilungen mittels der ,,Table-look-up-Methode"

Sei eine gleichverteilte Zufallsvariable und eine beliebige Verteilungsfunktion

einer stetigen Verteilung. Die Umkehrfunktion besitzt dann die gewünschte

Verteilung . Diese Umkehrfunktion kann dann als Zufallsvariable angesehen werden. Diese Methode wird auch Inversionsmethode genannt. Sie ist nur dann zulässig, wenn ein stetige Funktion ist, die streng monoton wächst.

Nachfolgend soll die Simulation einer exponentialverteilten Zufallsvariablen erläutert werden.

Dichtefunktion: für

Verteilungsfunktion:

um eine streng monoton wachsende Funktion handelt, ist es Da es sich bei der Funktion

zulässig die Inverse zu bilden.

Umkehrfunktion

Abbildung 4: Morgan S.96: Prinzip, nach der die ,,Table-look-up"-Methode für einen stetige Verteilung arbeitet.

Exponentialverteilte Zufallszahlen erhält man nun, indem man gleichverteilte Zufallszahlen aus dem Intervall [0,1] generiert und diese in die Umkehrfunktion einsetzt.

Beispiel für :

3.2.1.c) Simulation von standardnormalverteilten Zufallszahlen mittels der ,,Table-lookup"-Methode

Wenn standardnormalverteilte Zufallszahlen simuliert werden sollen, stößt die ,,Table-look- schnell an ihre Grenzen. Eine Bildung der Umkehrfunktion von der

Verteilungsfunktion der Standardnormalverteilung ist zwar möglich, sie ist jedoch nur doch aufwendige Approximationen zu realisieren. Durch die Anwendung eines Tricks ist jedoch eine Simulation möglich.

Zur Simulation dieser Zufallszahlen sind gleichverteilte Zufallszahlen aus dem Intervall [0,1[ wieder die Grundvoraussetzung. Die erzeugten Zufallszahlen werden anschließend mit der

der Standardnormalverteilung verglichen. vertafelten Verteilungsfunktion Nachfolgende Realisationen der -Verteilung werden durch -verteilte Zufallszahlen erzeugt:

Gleichverteilte Zufallszahlen < 0,5 erzeugen standardnormalverteilte Zufallszahlen <0, gleichverteilte Zufallszahlen >0,5 erzeugen standardnormalverteilte Zufallszahlen >0. Die Genauigkeit der erzeugten Zufallszahlen hängt dabei von der Genauigkeit der vertafelten

Verteilungsfunktion ab. Tabellen für die Verteilungsfunktion sind den Standardwerken der Statistik, z.B. Bamberg Baur, aufgeführt und können dort entnommen werden.

4 Erzeugung von Zufallszahlen in Microsoft Excel

4.1 Gleichverteilte Zufallszahlen

Durch den nachfolgenden Algorithmus werden gleichverteilte Zufallszahlen in Microsoft Excel generiert:

Restbruch von für alle

Der Startwert ist dabei abhängig von der Systemzeit. Mit Hilfe dieser Formel sind bis zu 1 Million verschiedene Zufallszahlen möglich.

Durch nachfolgende Formel kann die Erzeugung von gleichverteilten Zufallszahlen in Excel-Tabellen aus dem Intervall [0,1[ erreicht werden: =ZUFALLSZAHL( )

Sollen gleichverteilte, ganze Zufallszahlen aus einem Intervall erzeugt werden, so bietet Microsoft Excel folgende Funktion: )

Die Variable stellt dabei die untere Grenze dar, ist die obere Grenze. Mit Hilfe dieser Funktion werden ganze Zufallszahlen aus dem Intervall erzeugt.

5 Abschließende Beurteilung

Die vorliegende Arbeit hat gezeigt, daß jede Methode, sei es die zur Erzeugung von ,,echten" Zufallszahlen, als auch die von Pseudozufallszahlen, ihre Vor- und Nachteile hat. Hier hat der Benutzer zu entscheiden, nach welchem Prinzip er die benötigten Zufallszahlen erzeugen will.

Grundlage bei der Erzeugung von nicht gleichverteilten Zufallszahlen ist immer die Erzeugung von gleichverteilten Zufallszahlen aus dem Intervall [0,1[. Ist eine Methode bekannt, gleichverteilte Zufallszahlen zu erzeugen, so sind auch andere Verteilung zu simulieren, sowohl diskrete als auch stetige Verteilungen.

Desweiteren konnten in dieser Arbeit nur Ansätze für die Erzeugung von Zufallszahlen gegeben werden, es existieren jedoch noch weitere Möglichkeiten um Zufallszahlen zu generieren. Diese würden den Rahmen dieser Proseminararbeit jedoch sprengen.

6 Literaturverzeichnis

Zur Erstellung dieser Arbeit wurde folgende Literatur herangezogen:

1. Grundausbildung in Statistik für Wirtschaftswissenschaftler Autorenkollektiv Freie Universität Berlin Universität Bielefeld Technische Universität Hannover

2. Zufallszahlen für Simulationsmodelle Härtel, Frank 1994 Difo-Druck GmbH Bamberg

3. Elements of Simulation Morgan, Byon J.T. 1984 Chatman & Hall London - New York

4. Stochastic Simulation Ripley, Brian D. 1987 John Wiley & Sons, Inc.