Erzeugung von Zufallsvariaten und MCMC

Stochastische Simulation ist ein bekanntes und wichtiges Wergzeug in vielen Forschungsgebieten und Anwendungen. Grundlage dieser Technik ist jedoch, dass Zufallsvariate von vielen verschiedenen Verteilungen erzeugt werden können. Daher hat man bereits in den Fünfzigerjahren des letzten Jahrhunderts begonnen Methoden zu deren Erzeugung zu entwickeln. Im Vordergrund der hierbei entwickelten Algorithmen standen hohe Generierungsgeschwindigkeit und geringer Speicherverbrauch. Diese Algorithmen sind für spezielle Standardverteilungen maßgeschneidert. Sollen Zufallsvariate von einer anderen Verteilung oder für ein spezielles Simulationsproblem erzeugt werden, so ist ein neuer Algorithmus erforderlich. In den letzten zehn Jahren wurden sogenannte automatische Methoden entwickelt, die es ermöglichen mit Hilfe eines einzigen Computerprogrammes Zufallszahlen aus einer großen Klasse von Verteilungen zu erzeugen. Diese Algorithmen arbeiten relativ effizient und haben Eigenschaften, die sie auch für die Erzeugung von (z.B.) normalverteilten Zufallvariaten attraktiv machen. Der Preis, den man bei der Verwendung solcher Generatoren zu bezahlen hat, ist die Notwendigkeit eines Initialisierungsschrittes, der für manche Verteilungen/Methoden relativ zeitaufwendig sein kann. Obwohl in den letzten Jahren einige derartige Algorithmen entwickelt wurden, gibt es noch viele ungelöste Probleme. Im Bereich der Markov Chain Monte Carlo Methoden ist es notwendig, dass immer nur eine Zufallsvariate von einer Verteilung erzeugt wird; das aber sehr oft. Methoden mit schnellem Initialisierungsschritt wären daher wichtig. Methoden zur Erzeugung von unabhängigen multivariaten Zufallsvektoren sind von Bedeutung, aber die verfügbaren Algorithmen sind langsam oder arbeiten nur für wenige Dimensionen. Für Quasi-Monte Carlo Methoden (QMC) werden schnelle Algorithmen benötigt, die eine gegebene Folge von (gleichverteilten) Zahlentupel mit kleiner Diskrepanz in entsprechende Zufallsvektoren mit vorgegebener Dichte transformieren. Eine andere Problematik liegt darin begründet, dass die mathematischen Theorien, die diesen automatischen Methoden zugrunde liegen, von reellen Zahlen ausgehen. Implementiert werden diese Algorithmen jedoch in Computern die nur über eine Gleitkommaarithmetik mit begrenzter Genauigkeit verfügen, typischerweise 16 Dezimalstellen. Ziel dieses Forschungsprojektes ist es, Lösungen für diese und ähnliche Probleme zu erarbeiten.

Viele Beobachtungen, die wir in unserer Umwelt machen, können am besten durch sogenannte Zufallsprozesse beschrieben werden: Glückspiele, Verlauf von Aktienpreisen oder Verkaufszahlen, Evolutionstheorie, Passagieraufkommen eines Flughafens, u.v.m. Wahrscheinlichkeitsrechnung und Statistik bieten uns Werkzeuge um dieses Unvorhersehbare trotzdem handhaben zu können. Die beobachteten Größen werden durch Zufallsverteilungen beschrieben, die ihrerseits durch Parameter wie Mittelwert oder Varianz charakterisiert werden. Allerdings ist das Berechnen dieser Parameter bei komplexen Modellen schwierig. Sogenannte stochastische Simulation bietet eine überraschend einfache Lösung an: Für jede Zufallsgröße des Modells wird ein möglicher Wert erwürfelt und die Auswirkung auf die beobachtete Grösse errechnet; dieser Vorgang wird möglichst oft wiederholt und über alle Ergebnisse gemittelt. Wir erhalten dann einen Schätzwert für den gesuchten Parameter, der zumindest bis auf eine (von uns selbst bestimmte) Irrtumswahrscheinlichkeit gültig ist. Dieser einfache Ansatz eignet sich sogar für Probleme, die eigentlich gar keine Zufallskomponenten enthalten. In sogenannten randomisierten Algorithmen wird das ursprüngliche Problem durch stochastisches Problem mit gleichem Resultat ersetzt. Für beide Anwendungen hat sich der Name "Monte Carlo Methoden" eingebürgert. Entscheidend für das Funktionieren dieser Algorithm ist die Verfügbarkeit geeigneter Zufallszahlen. In der Praxis werden Pseudo- Zufallszahlen (also Zahlen die aussehen als wären sie echte Zufallszahlen) oder Quasi-Zufallszahlen (die gleichmässiger verteilt sind und daher genauere Ergebnisse versprechen) verwendet. Solche Zahlen werden in zwei Schritten erzeugt: Zuerst werden gleichverteilte Punktmengen generiert, die anschliessend geeignet transformiert werden. Für häufig verwendete Verteilungen ist dieses Problem gelöst. Es gibt aber immer wieder Situationen, in denen neue Algorithm für diesen Transformationsschritt notwendig werden. Ziel dieses Projekts war es, möglichst einfach zu verwendende Algorithmen zur Verfügung zu stellen. Ein Anwender braucht nur einige Informationen zu seiner gewünschten Verteilung bereitstellen und erhält dann vollautomatisch eine Zufallstichprobe. Wir haben diesen Werkzeugkasten auf mehrere Arten weiterentwickelt. Zum einem haben wir Speicherbedarf, Setupzeit oder Rechengenauigkeit von bereits existierenden Algorithmen verbessert, andererseits haben wir die Bedienung vereinfacht, indem schwierig zu bestimmende Informationen im Setup der Algorithmen berechnet werden. Wir haben außerdem einige neue Algorithmen vorgeschlagen, insbesondere für den schwierigen Fall vieler Dimensionen. Diese Algorithmen wurden alle implementiert, getestet und als quelloffene Programmbibliothek allen Interessenten zur Verfügung gestellt. Diese können in Computergrogramme eingebunden werden oder auch aus anderen interaktiven Arbeitsumgebungen heraus benutzt werden.