Universität Bonn

Institut für Informatik IV

Betriebssysteme und Stochastische Modellierung

Werner Sandmann: Simulation seltener Ereignisse

Bei der simulativen Bestimmung solcher kleinen Wahrscheinlichkeiten besteht das Problem darin, daß auch in der Simulation seltene Ereignisse selten auftreten. Dies führt dazu, daß bei Verwendung klassischer Verfahren die Rechenzeit selbst bei der rasant wachsenden Leistungsfähigkeit heutiger Computer so groß wird, daß die Simulationen praktisch nicht mehr durchführbar sind. Verfahren zur Beschleunigung solcher Simulationen sind also von großer Bedeutung.

Eine solche Simulationsbeschleunigung kann häufig durch ein im Kern schon recht altes Verfahren zur Varianzreduktion, das Importance Sampling, erreicht werden. Die Idee dabei besteht darin, das der Simulation zugrundeliegende Wahrscheinlichkeitsmaß so zu verändern, daß die seltenen Ereignisse häufiger auftreten, und dann die auf diese Weise systematisch verfälschten Ergebnisse mit einem Korrekturfaktor, dem Likelihood Ratio, auf das Originalproblem zurückzurechnen.

In der Praxis zeigt sich jedoch, daß die Art des Maßwechsels sehr starken Einfluß darauf hat, inwieweit und ob überhaupt eine Simulationsbeschleunigung (gleichbedeutend mit Varianzreduktion) erzielt wird oder sogar das Gegenteil erreicht wird. In einem bestimmten Sinne (asymptotisch) optimale Maßwechsel existieren bis heute lediglich für sehr eingeschränkte Modelle, wie z.B. M/M/1/K oder auch einige Tandemsysteme. Dazu gibt es zahlreiche Heuristiken, die gewisse Richtlinien für den Maßwechsel vorgeben oder auch zur Validierung von Ergebnissen dienen.

Ziel ist es, für möglichst allgemeine Markov-Modelle, für Markovketten, z.B. beschrieben durch Übergangsklassenmodelle oder auch in ihrer üblichen Form, solche beschriebenen optimalen Maßwechsel oder zumindest solche Maßwechsel, die eine Varianzreduktion erzielen, zu finden.