Inversionsmethode
Die Inversionsmethode ist eine bedeutende Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen diskreten oder stetigen Verteilung. Basis ist das Simulationslemma.
Simulationslemma
Idee
Das Simulationslemma ist ein Lemma, das besagt, dass man mit Hilfe einer Folge von Standardzufallszahlen zumindest theoretisch zu anderen univariaten Verteilungen eine Folge von Zufallszahlen erzeugen kann. Diese Idee mündet in der Inversionsmethode. Standardzufallszahlen genügen übrigens einer Rechteckverteilung mit den Parametern 0 und 1.
Sei eine Verteilungsfunktion. Ihre Pseudoinverse sei als definiert, wobei zwischen 0 und 1 liegen muss.
Sei nun eine Standardzufallszahl.
Dann ist eine Zufallsvariable, die der Verteilungsfunktion F genügt.
Beweis
.
Der letzte Schritt ist wegen der Rechteckverteilung von Standardzufallszahlen erfüllt.
Fazit
Zu vielen Verteilungsfunktionen ist es in der Praxis mit vertretbarem Aufwand nicht möglich, eine Pseudiinverse wie oben beschrieben zu bestimmen. Für viele Verteilungen, etwa die Normalverteilung, bleibt das Simulationslemma daher eine theoretische Idee.
Bei anderen Verteilungsfunktionen hingegen lassen sich unter Ausnutzung des Simulationslemma auf einfache Weise Zufallszahlen erzeugen.
Umsetzung
Die Verteilung von Zufallszahlen wird durch künstlich herbeigeführte Realisationen einer statistischen Zufallsvariablen nachgestellt. Man kann Zufallszahlen verschiedener diskreter und stetiger Wahrscheinlichkeitsverteilungen erzeugen. Diese Folgen von Zufallszahlen werden beispielsweise verwendet, um das Verhalten komplexer Systeme, die man nur unter Schwierigkeiten mit mathematischen Funktionen analysieren kann, zu untersuchen. Beispiele wären die Warteschlangentheorie oder die Verteilung von bestimmten Stichprobenfunktionen, etwa der nichtzentralen Betaverteilung.
Die Basis für die Erzeugung der Zufallszahl x einer bestimmten Verteilung F(x) ist in der Regel eine Rechteckverteilung oder Gleichverteilung im Intervall [0;1]. Die Generierung dieser Zufallszahlen ist im Artikel Zufallszahlengenerator genauer beschrieben. Man macht sich zu Nutze, dass auch die Verteilungsfunktion einen Wertebereich zwischen Null und Eins aufweist. Wählt man in diesem Intervall zufällig eine Zahl, so kann man sie als Wert einer Verteilungsfunktion F(x) interpretieren. Der dazugehörige Wert der Zufallsvariablen, das Quantil, ist dann die gewünschte Zufallszahl. Das Quantil ergibt sich gewissermaßen als Umkehrfunktion der entsprechenden Wahrscheinlichkeitsverteilung.
Eine genaue Beschreibung dieser Idee findet sich im Artikel Simulationslemma. Die Idee wird in der Inversionsmethode umgesetzt.
Diskrete Verteilung
Einfaches Beispiel: Zwei verschiedene Ausprägungen
In einer Porzellanfabrik werden Kaffekannen hergestellt. Die Henkel und Schnäbel der Kannen werden vor dem Brennen von Hand angeklebt. Erfahrungsgemäß sind 25% der Teile nicht ordnungsgemäß befestigt. Nach dem Brennen werden die Kannen nacheinander geprüft.
- Ist die Kanne in Ordnung, wird eine Eins vergeben: Das ist in 75% aller Kannen der Fall.
- Ist sie zu beanstanden, vergibt der Prüfer eine Zwei: Das kommt bei 25% aller Kannen vor.
Wir wollen nun eine Folge von Kannen simulieren:
Definieren wir die obige Vorgabe als Verteilung einer Zufallsvariablen X:
- P(X = 1) = 0,75
- P(X = 2) = 0,25
- Für alle anderen Werte von X ist P(X = x) = 0.
Man könnte nun so vorgehen: Es wird eine Zufallszahl Y im Intervall [0;1] erzeugt. Liegt Y zwischen 0 und 0,75, bekommt die Zufallszahl X den Wert 1, sonst den Wert 2. Auf diese Weise erzeugen wir 75% Einsen und 25% Zweien. Es ergibt sich also beispielsweise in der Tabelle unten eine Folge von (1;2)-Zufallszahlen. Die Grafik verdeutlicht den Vorgang der Zuordnung anhand des ersten Wertes. Die Gleichverteilung produzierte ein y = 0,3850. Hier wird x = 1 vergeben.
A: Nr. der Kanne B: Gleichverteilte Zufallszahl C: Zustand der Kanne A B C 1 0,39 1 2 0,34 1 3 0,41 1 4 0,93 2 5 0,05 1 6 0,44 1 7 0,95 2 8 0,43 1 9 0,07 1 10 0,77 1 11 0,02 1 12 0,93 2 13 0,68 1 14 0,26 1 15 0,94 2 16 0,88 2 17 0,23 1 18 0,91 2 19 0,51 1 20 0,69 1
Beispiel einer poissonverteilten Zufallszahl
Um den Kundenservice zu optimieren, wird die Zahl der Kunden erfasst, die innerhalb einer Minute an einen bestimmten Bankschalter kommen. Man weiß aus Erfahrung, dass pro Minute im Durchschnitt 1,2 Kunden an den Schalter kommen. Die Zahl der ankommenden Kunden soll simuliert werden. Eine gute Näherung für die Verteilung ist die Poissonverteilung mit dem Parameter Kunden/Minute. Ihre Werte für diesen Fall lauten:
x: Zahl der Kunden in einer Minute f(x): Wahrscheilichkeit für genau x Kunden F(x): Wahrscheilichkeit für höchstens --- x f(x) F(x) 0 0,3 0,3 1 0,36 0,66 2 0,22 0,88 3 0,09 0,97 4 0,03 0,99 5 ca.0 ca. 1
Analog zu oben verwenden wir hier die wieder Verteilung F(x) für die Simulation.
A: Minuten-Index: B: Gleichverteilte Zufallszahl: F(x) C: Zahl der neu hinzu kommenden Kunden: 1,2 Kunden / Minute: x D: Zahl der verbleibenden Kunden nach Bedienung von 1,5 Kunden / Minute (siehe unten) E: Wie D, gerundet auf ganze Zahlen (siehe unten) ---- A B C D E 1 0,63 1 0 0 2 0,55 1 0 0 3 0,21 0 0 0 4 0,93 3 1,5 2 5 0,85 2 2 2 6 0,96 3 3,5 4 7 0,81 2 4 4 8 0,68 2 4,5 5 9 0,88 2 5 5 10 0,04 0 3,5 4 11 0,51 1 3 3 12 0,07 0 1,5 2 13 0,28 0 0 0 14 0,59 1 0 0 15 0,55 1 0 0 16 0,68 2 0,5 1 17 0,61 1 0 0 18 0,08 0 0 0 19 0,57 1 0 0 20 0,56 1 0 0 21 0,52 1 0 0 22 0,1 0 0 0 23 0,27 0 0 0 24 0,17 0 0 0 25 0,72 2 0,5 1 26 0,06 0 0 0 27 0,55 1 0 0 28 0,92 3 1,5 2 29 0,72 2 2 2 30 0,03 0 0,5 1
In der ersten Minute liegt die gleichverteilte Zufallszahl y = 0,6270 zwischen 0,3012 und 0,6626, wie in der Grafik angedeutet. Hier erhält x den Wert 1.
In der zweiten Minute liegt y = 0,5508 wieder zwischen 0,3012 und 0,6626, x erhält wieder den Wert 1 usw.
Es ergibt also die Folge der ankommenden Kunden wie in der Tabelle.
Man könnte nun mit der Simulation untersuchen, ob die Schlange der Kunden sehr groß werden kann, ob man beispielsweise einen weiteren Schalter offenhalten sollte.
Exkurs in die Warteschlangentheorie
In einer sehr vereinfachte Systemsimulation wollen wir die entstehende Warteschlange der Bankkunden untersuchen: Im Mittel kommen, wie im Beispiel oben, 1,2 Kunden pro Minute. Bedient werden sollen im Durchschnitt 1,5 Kunden pro Minute. Mann könnte vermuten, dass es keine Warteschlangen gibt, weil ja im Mittel mehr Kunden bedient werden als ankommen. Eine Simulation mit der Poissonverteilung ergibt aber folgendes Bild:
Es haben sich in einer knappen Stunde Schlangen mit bis zu fünf Personen gebildet. Die Ursache liegt darin, dass die Bearbeitungskapazität in den Zeiträumen nicht genutzt wird, wenn keine Kunden anwesend sind (es gibt keine negativen Kunden).
Stetige Verteilung
Für die Verteilung einer stetigen Zufallsvariablen ergibt sich statt einer Treppenfunktion eine stetige, streng monoton steigende Verteilungskurve.
Die Verteilungsfunktion etwa der Exponentialverteilung ist
Als Umkehrfunktion erhalten wir dann
Beispiel für Exponentialverteilung
Die Zeit, die zwischen zwei Anfragen an einen bestimmten Wikipedia-Server liegt, sei exponentialverteilt mit dem Parameter . Es sollen die Zeiten x simuliert werden, die zwischen zwei Anfragen an den Server liegen.
Die Verteilungsfunktion
ist in der Grafik rechts dargestellt. Der Ordinatenwert F(x) entspricht der Zufallszahl y, der entsprechende Abszissenwert ist die gesuchte exponentialverteilte Zufallszahl.
Rechnerisch einfacher ist es, mit der Umkehrfunktion zu arbeiten und zu berücksichtigen, dass sich an den Zufallszahlen y aus dem Intervall [0,1] nichts ändert, wenn wir (1-y) durch y ersetzen:
In der Tabelle-1 ist eine Folge von exponentialverteilten Zufallszahlen dargestellt. Die Grafik unten gibt diese Zahlen als Zeitreihe wieder.
Tabelle-1 lambda = 2 Zugriffe / Zeiteinheit A: Index B: exponentialverteilte Zufallszahl C: B aufsummiert = Zeitpunkte des Eintreffens --- A B C 0 0,00 0,00 1 0,58 0,58 2 1,17 1,76 3 0,31 2,07 4 0,02 2,09 5 0,25 2,34 6 1,58 3,92 7 0,15 4,07 8 0,25 4,32 9 0,06 4,38 10 0,17 4,55 11 0,21 4,76 12 0,20 4,96 13 0,70 5,66 14 0,22 5,88 15 0,17 6,05 16 0,42 6,47 17 0,00 6,47 18 1,89 8,36 19 0,40 8,76 20 0,76 9,52 21 0,37 9,88 22 0,53 10,42 23 0,54 10,96 24 0,36 11,32 25 0,41 11,73 26 0,38 12,11 27 1,31 13,42 28 0,13 13,55 29 0,05 13,61 30 1,95 15,55 31 1,60 17,15 32 0,35 17,50 33 0,81 18,31 34 0,29 18,60 35 0,32 18,92 36 0,30 19,22 37 1,43 20,65 38 0,55 21,20 39 0,01 21,21 40 0,33 21,54 41 0,48 22,03 42 1,13 23,16 43 0,97 24,13 44 0,42 24,54 Mittelwert von B: 0,56 (berechnet: 1/lambda = 0,5) Standardabweichung von B: 0,51 (berechnet: 0,5)
Während die zeitliche Abfolge der Zugriffe exponentialverteilt ist, folgt die Zahl der Zugriffe pro Zeiteinheit einer Poissonverteilung. Beispielsweise werden 4 Intervalle beobachtet, innerhalb derer kein Ereignis auftritt und 8 Intervalle mit einem Ereignis, siehe Tabelle-2. Für die beiden Fälle macht die Poission-Verteilung die Vorhersagen von 3,1 bzw. 6,2 -- in Anbetracht der geringen Anzahl der Werte eine gute Übereinstimmung.
Tabelle-2 A: Zahl der Ereignisse pro Intervall, basierend auf C in Tabelle-1 B: Gemessene Ereignisse C: Berechneter Wert für E nach Poissonverteilung --- A B C 0 4 3,11 1 8 6,23 2 5 6,23 3 4 4,15 4 2 2,08 5 1 0,83 6 0 0,28
Normalverteilung
Verschiedene Ansätze zur Erzeugung normalverteilter Zufallszahlen sind im Artikel Normalverteilung, Abschnitt Simulation von normalverteilten Zufallsvariablen zusammen gefasst.
Bei der Erzeugung von multivariaten normalverteilten Zufallszahlen müssen die erzeugten stochastisch unabhängigen Zufallszahlen noch korreliert werden. Man erreicht das, indem die Datenmatrix der unabhängigen Zufallszahlen mit S1/2 multipliziert wird, wobei S die Kovarianzmatrix der korrelierten normalverteilten Zufallsvariablen ist (siehe Artikel dort).
Probleme
Nicht immer lassen sich die im Simulationslemma vorausgesetzten Pseudoinversen für stetige Verteilungsfunktionen erzeugen. Dann lässt sich die Inversionsmethode nicht anwenden.
Als Lösung bietet sich in solchen Fällen häufig die Verwerfungsmethode an.