title: Generalized continued fractions: definitions, convergence and applications to Markov Chains
Creators: name: Baumann, Hendrik
Publisher: name: MyCoRe Community
Year: 2017
Subjects: subject: verallgemeinerte Kettenbrüche
subject: Konvergenz
subject: algorithmische Methode für Markovketten
subject: 510

description: Markovketten werden in der mathematischen Modellierung in verschiedensten Anwendungsbereichen
verwendet, zum Beispiel in der Warteschlangentheorie (mit Anwendungen auf Produktionsnetze,
Telekommunikation, . . . ), in der Epidemiologie, bei der Analyse biochemischer
stochastischer Reaktionsnetze, . . .
In praktischen Anwendungen sind zunächst langfristige Kenngrößen der Markovketten von
großem Interesse, zum Beispiel die langfristige mittlere Anzahl von Kunden in einer Warteschlange.
Leider gibt es in den meisten aus der Modellierung praktischer Anwendung entstandener
Markovketten keine Möglichkeit, diese Kenngrößen explizit zu ermitteln, so dass
numerische Verfahren eingesetzt werden müssen. In den meisten realistischen und daher auch
detaillierten Modellen ist allerdings auch der Zustandsraum sehr groß, häufig unendlich groß.
Dann entstehen beim Einsatz numerischer Methoden Schwierigkeiten.
Ist die Übergangs- oder Generatormatrix einer Markovkette block-tridiagonal strukturiert, so
wird in der Literatur der Einsatz matrix-analytischer Verfahren zur algorithmischen Berechnung
der invarianten Verteilung (aus der stationäre Kenngrößen ermittelt werden können)
vorgeschlagen. Von diesen Verfahren ist bekannt, dass sie eng mit matrix-wertigen Kettenbrüchen verwandt sind. Ebenso wurden in der Literatur für Band-Matrizen Methoden eingeführt, die auf einer geeigneten Verallgemeinerung (reellwertiger) Kettenbrüche beruhen.
Die Band- oder block-tridiagonale Struktur einer Übergangs- oder Generatormatrix kann als
Einschränkung des dynamischen Verhaltens der Markovkette interpretiert werden: Ein Übergang
von Zustand i nach Zustand j kann nur erfolgen, wenn j in einer Art Nachbarschaft
von i liegt. In dieser Schrift wird diese Einschränkung fallengelassen: Es wird eine geeignete
Definition verallgemeinerter Kettenbrüche eingeführt, die es erlaubt, langfristige Kenngrößen
von Markovketten mit beliebiger Übergangsstruktur als verallgemeinerte Kettenbrüche darzustellen.
Anschließend gibt es Diskussionen zu
 praktischen Aspekten: Es wird gezeigt, wie die Darstellung als verallgemeinerte Kettenbrüche genutzt werden kann, um untere und obere Schranken für langfristige Kenngrößen Größen effizient zu berechnen.
 theoretischen Aspekten: Die (durch Anwendung auf Markovketten motivierte) gegebene
Definition verallgemeinerter Kettenbrüche wird mit Verallgemeinerungen von Kettenbrüchen aus der Literatur verglichen. Außerdem werden Konvergenzkriterien und
Abschätzungen zur Konvergenzgeschwindigkeit hergeleitet, die unabhängig von der Anwendung
auf Markovketten sind.
description: Markov chains are used as mathematical models in various areas of applications, e.g. queueing
systems (production networks, telecommunication, . . . ), epidemiology, biochemical stochastic
reaction networks, . . .
In practical applications, we are interested in computing long-run characteristics of Markov
chains, for example the long-run average number of customers in a queueing system. Un-
fortunately, in most situations we are not able to obtain explicit representations of these
characteristics, and thus, we have to use numerical procedures. In most realistic and thus
detailed models, the state space of the Markov chain is very large. Often, there are infinitely
many states. In these situations, the application of numerical methods becomes difficult.
If the transition probability matrix or generator matrix of the Markov chain has a block-
tridiagonal structure, literature suggests using matrix-analytic solution techniques for com-
puting the invariant distribution (from which we can obtain long-run characteristics), and it is
well-established that these methods are strongly related to matrix-valued continued fractions.
Similarly, for band structured matrices, techniques relying on appropriate generalizations of
(real-valued) continued fractions were introduced.
The block-tridiagonal or band structure of a transition probability or generator matrix can
be interpreted as a restriction of the dynamic behaviour of the Markov chain: a transition
from state i to state j can only occur if state j is in some kind of neighbourhood of state i.
In this thesis, we drop this restriction: We introduce an appropriate definition of generalized
continued fractions (gcfs) which enables us to represent long-run characteristics of Markov
chains with arbitrary transition structures in terms of gcfs. We discuss
 practical issues: We demonstrate how to use the representation of long-run characteri-
stics for efficiently computing lower and upper bounds.
 theoretical issues: We compare our definition of gcfs (which is motivated by the ap-
plication to Markov chains) with generalizations of continued fractions found in the
literature, and we derive convergence criteria and speed-of-convergence estimates for
gcfs which are independent of the application to Markov chains.