SciDok

Eingang zum Volltext in SciDok

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-24316
URL: http://scidok.sulb.uni-saarland.de/volltexte/2009/2431/


Reduction of acyclic phase-type representations

Pulungan, Muhammad Reza

pdf-Format:
Dokument 1.pdf (1.502 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Matrix <Mathematik> , Dreiecksmatrix , Algorithmus , Reduktion , Stochastisches Modell
Freie Schlagwörter (Deutsch): Azyklische Phasentypverteilung , Matrixdarstellung , Prozess-Kalkül
Freie Schlagwörter (Englisch): acyclic phase-type distributiuon , matrix , triangular matrix , algorithm , reduction , stochastic model , process calculus
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Hermanns, Holger (Prof. Dr.-Ing.)
Sprache: Englisch
Tag der mündlichen Prüfung: 27.05.2009
Erstellungsjahr: 2009
Publikationsdatum: 22.09.2009
Kurzfassung auf Englisch: Acyclic phase-type distributions are phase-type distributions with triangular matrix representations. They constitute a versatile modelling tool, since they (1) can serve as approximations to any continuous probability distribution, and (2) exhibit special properties and characteristics that usually make their analysis easier. The size of the matrix representations has a strong effect on the computational efforts needed in analyzing these distributions. These representations, however, are not unique, and two representations of the same distribution can differ drastically in size.
This thesis proposes an effective algorithm to reduce the size of the matrix representations without altering their associated distributions. The algorithm produces significantly better reductions than existing methods. Furthermore, the algorithm consists in only standard numerical computations, and therefore is straightforward to implement. We identify three operations on acyclic phase-type representations that arise often in stochastic models. Around these operations we develop a simple stochastic process calculus, which provides a framework for stochastic modelling and analysis. We prove that the representations produced by the three operations are "almost surely" minimal, and the reduction algorithm can be used to obtain these almost surely minimal representations. The applicability of these contributions is exhibited on a variety of case studies.
Kurzfassung auf Deutsch: Azyklische Phasentypverteilungen sind Phasentypverteilungen, deren Matrixdarstellung eine Dreiecksmatrix ist. Sie stellen ein vielseitiges Modellierungswerkzeug dar, da sie einerseits als Approximationen jeder beliebigen kontinuierlichen Wahrscheinlichkeitsverteilung dienen können, und andererseits spezielle Eigenschaften und Charakteristiken aufweisen, die ihre Analyse vereinfachen. Die Größe der Matrixdarstellung hat dabei einen starken Einfluss auf den Berechnungsaufwand, der zur Analyse solcher Verteilungen nötig ist. Die Matrixdarstellung ist jedoch nicht eindeutig, und zwei verschiedene Darstellungen ein und derselben Verteilung können sich drastisch in ihrer Größe unterscheiden.
In dieser Arbeit wird ein effektiver Algorithmus zur Verkleinerung der Matrixdarstellung vorgeschlagen, der die mit der Darstellung assoziierte Verteilung nicht verändert. Dieser Algorithmus verkleinert die Matrizen dabei beträchtlich stärker als bereits existierende Methoden. Darüberhinaus bedient er sich nur numerischer Standardverfahren, wodurch er einfach zu implementieren ist. Wir identifizieren drei Operationen auf azyklischen Phasentypdarstellung, die in stochastischen Modellen häufig anzutreffen sind. Von diesen Operationen ausgehend entwickeln wir einen einfachen stochastischen Prozess-Kalkül, der eine grundlegende Struktur für stochastische Modellierung und Analyse darstellt. Wir zeigen, dass die durch die drei Operationen erzeugten Darstellungen "beinahe gewiss" minimal sind und dass der Reduktionsalgorithmus benutzt werden kann, um diese beinahe gewiss minimalen Darstellungen zu erzeugen. Die Anwendbarkeit dieser Beiträge wird an einer Reihe von Fallstudien exemplifiziert.

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English