Problemstellung  |  |
| Von der Gleichverteilung in andere Verteilungen | |
Für die meisten stochastischen Simulationen ist mit gleichverteilten Zufallszahlen nur ein Teil des Problems gelöst. Häufig soll etwas anderes als eine Gleichverteilung auf einem bestimmten Intervall aus den ganzen Zahlen oder eine Gleichverteilung auf dem Intervall von 0 bis 1 simuliert werden. Zufallszahlen oder Pseudozufallszahlen liegen aber in den meisten Fällen in dieser Form vor.
Im Grenzbereich von Softwareentwicklung und Statistik stellt sich nun das Problem, dass man gleichverteilte Zufallszahlen aus dem Einheitsintervall hat, aber Zufallszahlen benötigt, die einer bestimmten statistischen Verteilung folgen. Deswegen sind für Simulationsprogramme Transformationen erforderlich.
Für diese Transformationen ist es meistens unerheblich, ob die zugrundeliegenden Zufallszahlen echte ZufallsZahlen, Pseudozufallszahlen oder Quasizufallszahlen sind.
Die Vorgehensweise ist dabei teilweise direkt aus statistischen Methoden abzuleiten, die eine Zufallsgroesse transformieren, teilweise ist sie auch sehr stark an den Möglichkeiten von Computerprogrammen orientiert.
| Von einer Gleichverteilung auf ganzen Zahlen in eine Gleichverteilung auf dem Einheitsintervall | |
Die Abbildung des Intervalls [0, 2^d-1] auf [0, 1) ist am Einfachsten: Man dividiert einfach durch 2^d. In einer IEEE 754 konformen Gleitpunkt Arithmetik ist diese Division für d kleiner 23 (52 bei doppelter Genauigkeit) ohne numerische Verluste. Da nur 2^d verschiedene Werte auftreten können werden natürlich nicht alle möglichen Gleitpunktzahlen aus dem Einheitsintervall erzeugt, dafür ist die Transformation ein-eindeutig und erhält alle stochastischen Eigenschaften.
Das verwandte Einheitsintervall ohne Null ergibt sich, wenn die Null als Spezialfall behandelt und auf die Eins abbildet wird.
Abbildungen auf das komplette Einheitsintervall, Werte aus einem Bereich [0, 2^d-1] mit einem zu großen d oder Intervalle, die nicht 2^d Elemente enthalten sind dann ein eigenes Thema, da hier tiefergehende numerische Überlegungen eine Rolle erhalten.
Auch bei Überlegungen zu Eigenschaften der durch einer Transformation erzeugten Pseudozufallszahlen darf der Gesichtspunkt nicht aus den Augen verloren werden, dass die Ausgangsverteilung in Wirklichkeit eine Gleichverteilung auf endlich vielen rationalen Zahlen aus dem Einheitsintervall ist.
| Theorienahe Transformationen | |
Verfahren, die zur Transformation von Zufallszahlen geeignet sind, können grundsaetzlich auch für die Transformation von Pseudozufallszahlen verwendet werden. Wenn also im folgenden von Zufallszahlen die Rede ist, sollte stets klar sein, dass das gleiche Verfahren auch für Pseudozufallszahlen anwendbar ist, nur das das Ergebnis dann eben Pseudozufallszahlen aus der Zielverteilung sind.
Unter U soll im weiteren stets eine Zufallszahl aus der Gleichverteilung auf dem Einheitsintervall verstanden werden, unter X eine Zufallszahl aus der Zielverteilung
| Inverse Wahrscheinlichkeitstransformation | |
Für alle Verteilungen mit einer umkehrbaren Verteilungsfunktion F gibt es eine bestechend einfache Möglichkeit, Zufallszahlen aus einer Gleichverteilung auf dem Einheitsintervall in Zufallszahlen mit dieser umkehrbaren Verteilungsfunktion zu transformieren. Wenn G die Umkehrfunktion der Verteilungsfunktion ist, dann hat Zufallszahl G(U) hat die gewünschte Verteilung.
Für ein Simulationsprogramm ist diese Methode natürlich nur leicht anwendbar, wenn die Umkehrfunktion der Verteilungsfunktion nicht nur existiert, sondern auch effizient zu berechnen ist. Trotzdem bleibt die inverse Wahrscheinlichkeitstransformation die Notlösung für alle Fälle, in denen es keine bessere Möglichkeit gibt, auch wenn die Umkehrfunktion der Verteilungsfunktion nur numerisch bestimmbar ist. Geradezu ideal geeignet ist diese Methode für die Verteilungen, bei denen die Umkehrfunktion der Verteilungsfunktion eine einfache Form hat. Im einzelnen sind dies zum Beispiel
| Ausnutzen theoretischer Zusammenhaenge zwischen Verteilungen | |
Viele Verteilungen hängen exakt mit anderen Verteilungen zusammen oder sind Grenzverteilungen anderer Verteilungen beim einem Grenzübergang eines Parameters. Im Allgemeinen handelt es sich dabei um den Grenzübergang gegen unendlich.
Diese Zusammenhänge sind manchmal sehr gut geeignet, um Zufallszahlen aus einer weniger zugänglichen Zielverteilung zu erzeugen, indem man Zufallszahlen aus zugänglicheren Vertteilungen geeignet kombiniert.
Manchmal sind diese Zusammenhänge aber nicht geeignet, Zufallszahlen aus einer bestimmten Zielverteilung zu erhalten, auch wenn ein solcher Zusammenhang oft verlockend erscheint.
| Beta-verteilte Zufallszahlen aus Gamma-verteilten Zufallszahlen | |
Die Beta(a,b)-Verteilung ist definiert als die Verteilung von G / (G + H), wobei G Gamma-verteilt ist mit dem Parameter a und H Gamma-verteilt ist mit dem Parameter b.
Steht ein effizientes Verfahren zum Erzeugen von Pseodozufallszahlen aus einer Gamma-Verteilung zur Verfügung, dann kann dieser Zusammenhang genutzt werden, um Pseudozufallszahlen aus eine Beta-Verteilung zu erzeugen, ohne eine inverse Wahrscheinlichkeitstransformation anwenden zu müssen.
| Standard-normalverteilte Zufallszahlen aus gleichverteilten Zufallszahlen | |
Oft wird vorgeschlagen, standard-normalverteilte Zufallszahlen nach folgendem Algorithums aus auf dem Einheitsintervall gleichverteilten Zufallszahlen zu erzeugen:
|
|
Dieses Verfahren ist durch den zentralen Grenzwertsatz motiviert. Die Normalverteilung ist die Grenzverteilung der Summe von unabhängigen, identisch verteilten Zufallszahlen, wenn die Zahl der Summanden gegen unendlich geht. 12 ist aber von unendlich zu deutlich verschieden, um dieses Verfahren empfehlenswert zu machen - trotz seiner bestechenden Einfachheit.
Was hier verloren geht ist nicht die Gestalt der Dichte im Intervall [-6, 6], sondern die Möglichkeit von Realisationen ausserhalb dieses Intervalls. Wenn es auf die Möglichkeit von Ausreissern nicht ankommt, oder wenn ohnehin eine abgeschnittene Normalverteilung erzeugt werden soll, dann ist dieses Verfahren verwendbar.
| Ausnutzen geometrischer Eigenschaften von Verteilungen | |
| Box-Mueller-Transformation zum Erzeugen von Zufallszahlen aus einer zweidimensionalen Normalverteilung | |
Ein Vektor U = (U1, U2), der aus einer Gleichverteilung auf dem Einheitskreis gewählt wurde, kann in ein Paar von Zufallszahlen aus zwei unabhängigen Normalverteilungen transformiert werden.
|
|
Mit dieser Transformation läßt sich auch eine Zufallszahlengenerator für standardnormalverteilte Pseudozufallzahlen [BoxGenerator] bauen. Weil dabei aus Effizienzgründen ein Zustand gespeichert werden sollte, bietet sich eine objektorientierte Implementation an.
| Transformationstechniken | |
| Einbetten und Zurückweisen (Rejection Sampling) | |
Eine sehr allgemein anwendbare Transformationstechnik ist die Transformation einer Zufallszahl aus einer leicht zugänglichen Verteilung in eine schwerer zugängliche Verteilung, deren Dichte bekannt ist. Die Zufallszahl wird zunächste aus der leicht zugänglichen Verteilung gezogen. Dann werden die Dichten der leicht zugänglichen und der gewünschten Verteilung an der Stelle der Zufallszahl verglichen. Die Dichte der leicht zugänglichen Verteilung muss dabei so skaliert werden, dass sie überall grösser oder gleich der Dichte der Zielfverteilung ist. Jetzt wird das Verhältnis der Dichte der Zielverteilung zur Dichte der (möglicherweise skalierten) leicht zugänglichen Verteilung gebildet. Mit Hilfe einer weiteren Zufallszahl aus der Gleichverteilung auf dem Einheitsintervall wird dann entschieden, ob die Zufallszahl angenommen wird. Sie wird dann angenommen, wenn die Zufallszahl aus dem Einheitsintervall kleiner oder gleich dem Verhältnis der beiden Dichten ist.
Zu diesem Verfahren gibt es einen wichtigen Spezialfall: Wenn das Verhältnis der Dichten nur den Wert 0 oder eine Konstante sein kann, dann genügt es, Zufallszahlen aus der leicht zugänglichen Verteilung zu ziehen und diese zurückzuweisen, wenn die Dichte der Zielverteilung an der Stelle der Zufallszahl 0 ist. In diesem Spezialfall ist keine weitere Zufallszahl aus der Gleichverteilung auf dem Einheitsintervall erforderlich.
| Transformation in eine Gleichverteilung auf einem anderen Intervall | |
Zur Transformation einer Gleichverteilung V auf den ganzen Zahlen {0, ..., M} in eine Gleichverteilung X auf den ganzen Zahlen {L, ..., H} wird manchmal ein Verfahren vorgeschlagen, das den Divisionsrest verwendet.
|
|
Dieses Verfahren hat den Nachteil, dass es ungleichmaessig viele ganze Zahlen aus {0, ..., M} auf Zahlen in {L, ..., M} abbildet. Hier müssen im allgemeinen Zahlen aus {0, ..., M} abgewiesen werden, nämlich solche, die grösser oder gleich den grössten ganzzahligen Vielfachen von (H - L + 1) sind, das noch kleiner oder gleich M ist. Dieses Verfahren ist eine Anwendung der Transformation durch Einbetten (in eine Verteilung, bei der das Verhältinis der Dichten oder Wahrscheinlichkeitsfunktionen entweder 0 oder konstant ist) und Zurueckweise (in diesem Fall der unerwünschten Werte)
| Weitere Anwendungsbeispiele | |
| Ausgeglichene Suchbäume und diskrete Verteilungen mit endlichem Träger | |
Ein effizientes Verfahren zur Transformation von auf den Einheitsintervall gleichverteilten Zufallszahlen in Zufallszahlen aus einer diskreten Verteilung mit endlichem Träger setzte eine effiziente Abbildung von Intervallen aus dem Einheitsintervall auf Elemente des Trägers voraus. Der Wertebereich der Schlüssel dieser Abbildung sind disjunkte Teilintervalle aus dem Einheitsintervall. Die Suchvorgabe in dieser Abbildung ist eine einzelne Realisation aus U. Diese soll auf den Wert abgebildet werden, der durch die Abbildung dem Teilintervall zugeordnet ist, das die Suchvorgabe enthält.
Eine Technik zur Implementation von Abbildungen sind ausgeglichene oder beinahe ausgeglichene Suchbäume. Die Besonderheit der hier benötigten Suchbäume ist, dass die natürliche Vergleichsoperation zwischen der Suchvorgabe und dem Schlüssel hier kleiner, größer oder "enthalten" zurueckliefert.
| Fragen und Antworten | |