Phase Type Distributions, Volume 2 (eBook)

Theory and Application

András Horváth, Miklós Telek (Autoren)

eBook Download: EPUB

2024
431 Seiten
Wiley-Iste (Verlag)
978-1-394-32990-8 (ISBN)

Infos

Phase type distributions are widely applicable modeling and statistical tools for non-negative random quantities. They are built on Markov chains, which provide a simple, intuitive stochastic interpretation for their use. Phase Type Distribution starts from the Markov chain-based definition of phase type distributions and presents many interesting properties, which follow from the basic definition.
As a general family of non-negative distributions with nice analytical properties, phase type distributions can be used for approximating experimental distributions by fitting or by moments matching; and, for discrete event simulation of real word systems with stochastic timing, such as production systems, service operations, communication networks, etc. This book summarizes the up-to-date fitting, matching and simulation methods, and presents the limits of flexibility of phase type distributions of a given order.
Additionally, this book lists numerical examples that support the intuitive understanding of the analytical descriptions and software tools that handle phase type distributions.

András Horváth is Associate Professor at the University of Turin, Italy. His research interests include analysis and optimization of stochastic models with applications in production systems, service operations, communication networks and systems biology.
Miklós Telek is a professor in the Department of Networked Systems and Services at Budapest University of Technology and Economics, Hungary, where he currently heads the Information Systems Research Group of the Hungarian Research Network. His research interests include stochastic performance modeling, analysis and optimization of computer and communication systems.

Textauszug

Introduction

I.1. The benefits and the limitations of the exponential distribution

During the development of the theory of stochastic processes, many specific models got introduced for describing different real life phenomena. With respect to the contents of this book, the introduction of the Poisson process to model phone calls occurring in a period of time by A. K. Erlang played a seminal role [BRO 60a]. A. K. Erlang also recognized that the inter-arrival time of consecutive call arrivals is exponentially distributed.

Starting from the first specific stochastic processes, various generalizations were introduced to extend their modeling power. One of the simplest and analytically tractable general stochastic models, which got very popular in many application fields, is the class of Markov chains. In continuous time, a characteristic property of Markov chains is that, at any point in time, the next event occurs in an exponentially distributed amount of time, while in discrete time, the next event occurs in a geometrically distributed number of steps. Both of these distributions enjoy the memoryless property which means that, at any point in time, the remaining time to the next event is independent of the time elapsed since the last one.

Markov chains are very efficient modeling tools for such real life processes where the inter-event times are exponentially (geometrically) distributed, and, as observed by A. K. Erlang in the case of phone call arrivals, many practically important real systems enjoy this property. Unfortunately, it does not apply to all real systems. In spite of this, due to the theoretical simplicity and computational tractability of Markov chains, in many cases, real life processes are modeled by Markov chains also when the inter-event times of the real process are significantly different from being exponentially distributed. One reason for this is that the stochastic behavior of systems with non-exponentially (non-geometrically) distributed inter-event times is often too complex to analyze.

I.2. Phase-type distributions

In order to have models that provide both the analytical tractability of Markov chains and the possibility to describe non-exponentially distributed inter-event times, simple stochastic models have been introduced using the exponential distribution as a building block. It was recognized already by A. K. Erlang [BRO 60b] that the sum of two independent exponentially distributed random variables has a distribution that is different from exponential. A generalization of this observation leads to apply serial and parallel compositions of exponential random variables to approximate non-exponential inter-event time distributions. This approach is referred to as the method of phases in [KLE 75], where its applicability was questioned due to the lack of a general theorem which unifies the use of special (e.g. serial and parallel) structures.

The general theory of such distributions, which exploits the whole flexibility associated with a Markov chain of a finite number of states (referred to as phases), has been introduced by M. Neuts in [NEU 75], and the associated distribution got widely referred to as continuous phase type (continuous phase type (PH)) distributions.

The introduction of PH distributions resulted in a fertile research in the stochastic modeling community. Many essential questions have been investigated in order to understand the applicability of PH distributions regarding both:

• basic properties of PH distributions, such as,
  • - what is the density function and the moments of a PH distribution;
  • - whether the Markov chain based description of a PH distribution is unique;
  • - how many parameters identify a PH distribution of n phases;
• their use for approximation of a general non-negative distribution, for example,
  • - are there efficient procedures to find a PH distribution that closely approximates the general one;
  • - what are the appropriate measures of “goodness” of the approximation.

The complete summary of the literature on PH distributions in a single book is an infeasible task. In this book, we provide a large portion of the obtained results focusing mostly on the application of PH distributions in approximating general non-negative distributions. To this end, we collect qualitative properties of PH distributions that imply limitations in distribution fitting. For example, we present bounds on the moments of PH distributions, the behavior of the tail of PH distributions, etc. These qualitative properties help to set proper expectations about the quality of distribution approximation. For example, if the moments of a distribution are out of the moment bounds of the considered class of PH distributions, then accurate distribution approximation is infeasible even with the best approximation procedure.

We discuss two distribution approximation approaches which are referred to as matching and fitting. Matching takes a set of characterizing parameters (e.g. a set of moments) and composes a PH distribution with exactly the same parameters, if possible. If the selected parameters properly captures the distribution, then the approximation has good precision but it is still not exact in general.

Fitting is instead an optimization problem. It is based on a distance measure between two distributions and applies an optimization procedure to set the parameters of the PH distribution such that the distance measure is minimized.

Apart of these main lines of the book, we point out to various extensions which improve the applicability of PH distributions in different fields. As an example, we discuss the efficient simulation of PH distributions.

Besides the favorable properties of PH distributions in distribution approximation, another essential ingredient of their success and popularity is a set of efficient computational procedures to evaluate the behavior of stochastic models which contain PH distributions. A part of these procedures is referred to as matrix analytic methods [NEU 81c]. The treatment of these methods is out of the scope of this book.

I.3. The structure of the book

After the introduction, in Chapter 1, we collect most of the mathematical background which we use in later chapters. Readers who are familiar with the analysis of Markov chains might skip this chapter and return only when a piece of background information becomes of interest where it is used.

Chapters 2 and 3 introduce continuous time and discrete time PH distributions, respectively, and investigate their basic properties, like the distribution function, moments, etc. Additionally, many other useful properties are studied that characterize the flexibility of these classes of PH distributions.

Chapter 4 gives an outlook toward more general classes of distributions that have similar applicability as PH distributions but lack a stochastic interpretation based on the associated Markov chains.

The application of PH distributions started with special combinations of exponentially distributed random variables. Still today, certain subclasses of PH distributions play an important role in many applications. Chapter 5 summarizes the most frequently used subclasses and their properties.

Chapters 6 and 7 address the approximation of positive distributions with PH distributions. The first one discusses the matching approaches while the second one discusses the fitting methods and their respective properties.

When PH distributions are used in complex stochastic models whose complexity require discrete event simulation-based evaluation, the efficient simulation of PH distributions is of essential importance. Chapter 8 is devoted to this subject.

The analytical tractability and flexibility of PH distributions resulted in a line of research where various functions of PH-distributed random variables are applied to approximate distributions with special properties. The final chapter, Chapter 9, summarizes the related results.

Along the text, many numerical examples and related figures help the intuitive understanding of the presented materials. For numerical experimentation with PH distributions, readers can use many program packages that deals with PH distributions in general, for example, BuTools [BUT 15], SMCSolver [BIN 06] and KPC-Toolbox [CAS 08]. There are also a large number of more specific software tools to perform PH distribution fitting tasks, for example, HyperStar [REI 13] and PH-fit [HOR 02]. A short description of some tools is given in Appendix 1.

The previous literature on PH distributions also contains excellent textbooks that overview many properties of PH distributions. Some of these textbooks restrict their attention to a specific PH distribution related matters, for example, [BLA 17] which deals with matrix exponential distributions, and many other textbooks, in contrast to the present one, consider also the stochastic processes built from PH distributions (e.g. [NEU 81c], [BUC 14], [HE 14], [LAK 19]).

The basic properties of PH distributions are well summarized in each of these textbooks and we provide them also here for the sake of completeness. For what concerns the more involved properties, we present many specific features of PH distributions which have not been described in previous textbooks, for example, the eigenvalue structure in sections 2.8 and 3.7, the steepest increase...

Produkt-Details

• Erscheint lt. Verlag: 29.10.2024
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• ISBN-10: 1-394-32990-3 / 1394329903
• ISBN-13: 978-1-394-32990-8 / 9781394329908