Simulation seltener Ereignisse mittels Importance Sampling unter besonderer Berücksichtigung Markovscher Modelle

Abstract

Diese Arbeit behandelt die simulative Analyse seltener Ereignisse und dabei insbesondere die statistische Schätzung von Wahrscheinlichkeiten seltener Ereignisse unter Verwendung des Varianzreduktionsverfahrens "Importance Sampling", wobei ein besonderer Schwerpunkt auf Markovschen Modelle liegt, die in zahlreichen Anwendungsbereichen weit verbreitet sind.<br /> Seltene Ereignisse treten mit extrem kleiner Wahrscheinlichkeit auf, können dann aber katastrophale Auswirkungen haben. Man denke etwa an einen Super-GAU in einem Atomreaktor, den Ruin von Versicherungen oder Banken, Ausfälle von Fabrikationsanlagen, Schäden in technischen Systemen aufgrund von Materialermüdung, Überschreitung gefährlicher Schranken in ökologischen Systemen wie beispielsweise bei Flutkatastrophen oder speziell in Computer- und Kommunikationssystemen an Bitfehler in digitalen Datenübertragungssystemen, Komponentenausfälle in Computersystemen mit hohen Zuverlässigkeitsanforderungen, Verluste von Datenpaketen oder exzessive Warte- und Verzögerungszeiten in Rechnernetzen. In der modellbasierten Bewertung der Leistung und Zuverlässigkeit realer Systeme werden häufig Markovsche Modelle eingesetzt. Selbst unter der vereinfachenden Markovschen Annahme stellt sich jedoch für realistisch dimensionierte Modelle realer Systeme das Problem des exponentiell mit der Anzahl von Modellkomponenten anwachsenden Zustandsraums, die sogenannte Zustandsraumexplosion. Damit sind in der Regel traditionelle analytische oder numerische Verfahren nicht mehr effektiv durchführbar. Seltene Ereignisse schränken darüberhinaus auch die Effizienz fortgeschrittener Verfahren erheblich ein. Damit ist die Motivation für die Simulation seltener Ereignisse gegeben. Da seltene Ereignisse aber auch in Simulationen selten auftreten und für zuverlässige statistische Schätzungen eine hinreichend große Anzahl von Beobachtungen der interessierenden Ereignisse erforderlich ist, ergibt sich die Notwendigkeit zur Simulationsbeschleunigung durch Varianzreduktionsverfahren. Ein solches Verfahren ist Importance Sampling. Dabei wird das Ziel verfolgt, die interessierenden seltenen Ereignisse häufiger hervorzurufen, indem die Simulation mit Hilfe der Technik des Maßwechsels unter einem modifizierten Wahrscheinlichkeitsmaß durchgeführt wird. Die systematisch verfälschten Ergebnisse werden dann durch einen Korrekturfaktor, den Likelihood-Quotienten, auf das originale Wahrscheinlichkeitsmaß zurückgerechnet, um erwartungstreue Schätzer zu erhalten. Die Effizienz des Importance-Sampling-Schätzers, seine Varianz und die Breite resultierender Konfidenzintervalle, hängt dabei wesentlich vom gewählten Maßwechsel ab. <br /> Die Arbeit gibt zunächst eine grundlegende Einführung in die Beschreibung und analytische Behandlung seltener Ereignisse mittels der Theorie großer Abweichungen, ohne die viele der in der Literatur diskutierten Verfahren zur Simulation seltener Ereignisse und die Grenzen der Anwendbarkeit kaum verständlich und nachvollziehbar sind. Nach der Verdeutlichung der Probleme, die sich bei der zuverlässigen simulativen Schätzung der Wahrscheinlichkeiten seltener Ereignisse ergeben, werden die Grundlagen von Importance Sampling dargestellt. Es werden optimale Schätzer diskutiert, der Zusammenhang von Effizienzkriterien untersucht und die Grenzen traditioneller Strategien für den Maßwechsel aufgezeigt. Für Markovsche Modelle werden optimale Schätzer zunächst für Beispielmodelle und dann für allgemeine Klassen von Leistungsmaßen, für transiente und stationäre Wahrscheinlichkeiten, hergeleitet. Dabei wird gezeigt, daß der optimale Maßwechsel im allgemeinen aus der Klasse Markovscher Modelle herausführt. Importance Sampling wird auf strukturiert durch Transitionsklassen beschriebene Modelle angewendet, dabei Konzepte und Maßwechselstrategien präsentiert. Speziell für Markovsche Tandemwarteschlangennetze werden Maßwechsel entwickelt, die effiziente Schätzer für Überlauf- und Verlustwahrscheinlichkeiten liefern. Numerische Ergebnisse verdeutlichen die Effizienzsteigerung gegenüber anderen Verfahren. Das Prinzip der adaptiven Optimierung von Importance-Sampling-Schätzern wird vorgestellt, und die adaptive Optimierung dynamischer Maßwechsel für Transitionsklassenmodelle entwickelt. Zudem wird die immer mehr an Bedeutung gewinnende Cross-Entropy-Methode erläutert, deren Anwendungsbereich auf Transitionsklassenmodelle erweitert und ein direkter Zusammenhang der Methode zur Theorie großer Abweichungen hergestellt.