Reduction of acyclic phase-type representations

Abstract

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.

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.