Generalized continued fractions: definitions, convergence and applications to Markov Chains
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.
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.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
