Phase Type Distributions
Description
More details
Other editions
Additional editions
Persons
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.
Content
Introduction xi
Chapter 1 Mathematical Background 1
1.1. Basic properties of random variables 1
1.2. Moments of random variables and related quantities 2
1.3. Laplace transformation 3
1.4. z transform 4
1.5. Matrix functions of quadratic matrices 5
1.6. Matrix inverse 5
1.7. Eigenvalues and the characteristic polynomial 5
1.8. Spectral decomposition 6
1.9. Ordinary differential equation of vector functions 10
1.10. Exponential distribution 11
1.11. Erlang distribution 12
1.12. Discrete time Markov chain 12
1.13. Continuous time Markov chain 14
1.14. Kronecker algebra 15
Chapter 2. Continuous Phase Type Distributions 19
2.1. Definition and basic properties 19
2.2 Stochastic meaning of (-A)-123
2.3. Rational Laplace transform 24
2.4. Decomposition of matrix exponential functions 26
2.5. Similarity transformation 30
2.5.1. Similarity transformation with identical sizes 30
2.5.2. Similarity transformation with different sizes 31
2.5.3. Full rank representation 32
2.6. Closure properties 32
2.7 Positive density on (0, 1) 34
2.8. Eigenvalue structure 35
2.9. Steepest increase property 39
Chapter 3. Discrete Phase Type Distributions 43
3.1. Definition and basic properties 43
3.2 Stochastic meaning of (I-B)-1 45
3.3. Rational z transform function 46
3.4. Decomposition of the matrix geometric function 46
3.5. Similarity transformations 48
3.6. Closure properties 48
3.7. Eigenvalue structure 49
Chapter 4. Matrix Exponential and Matrix Geometric Distributions 51
4.1. Matrix exponential distributions 51
4.1.1. Non-negative matrix exponential subclasses 53
4.2. Matrix geometric distributions 54
Chapter 5. Classes and Representations of Continuous Phase Type Distributions 57
5.1. Number of parameters 57
5.2. Representations of continuous phase type distributions 58
5.2.1. Matrix representation 58
5.2.2. Markovian representation 58
5.2.3. Laplace representation 59
5.2.4. Moment representation 59
5.3. Transformations between continuous phase type representations 60
5.3.1. From matrix and Markovian representations to Laplace and moment representations 60
5.3.2. From Laplace representation to moment representation 60
5.3.3. From moment representation to matrix representation 60
5.3.4. From Laplace representation to matrix representation 61
5.3.5. From matrix representation to Markovian representation 61
5.4. Properties of the matrix representation of PH(n) distributions 62
5.4.1. 2n-1 versus n2 + n-1 parameters 62
5.4.2. Different matrix representations 63
5.5. Subclasses of continuous phase type distributions 65
5.5.1. Subclasses with real eigenvalues 65
5.5.2. Subclasses with complex eigenvalues 73
5.6. Canonical Markovian representation 76
5.7. Analysis of a non-Markovian representation 77
5.7.1. Monocyclic representation 81
5.7.2. Transformation to a Markovian representation 82
5.8. Representation minimization 85
5.8.1. Numerical issues 86
5.9. Markovian representation minimization 86
Chapter 6. Moment Matching 89
6.1. Continuous phase type distributions with minimal squared coefficient of variation 89
6.2. Moment bounds of continuous phase type distributions based on the steepest increase property 96
6.3. Matrix exponential distributions with minimal squared coefficient of variation 99
6.3.1. Matrix exponential distributions with complex eigenvalues 99
6.3.2. Matrix exponential distributions with real eigenvalues 104
6.4. Characteristics of moments of continuous phase type and matrix exponential distributions 107
6.5. Matching 2n-1 moments with size n matrix representations 114
6.5.1. Padé approximation for continuous distributions 114
6.5.2. Padé approximation for discrete distributions 118
6.6. Matching any three moments with minimal acyclic phase type distributions 120
6.6.1. Moment bounds 121
6.6.2. Explicit moment matching with minimal number of parameters 126
6.6.3. Proof of theorem 6.28 130
6.6.4. Proof of theorem 6.29 136
6.7. Matching any valid odd number of moments with generalized hyper-Erlang distributions 137
6.7.1. Moment matching procedure for generalized hyper-Erlang distributions 137
6.7.2. Numerical examples 140
6.8. Matching probability density function at zero 145
6.8.1. Numerical examples 146
6.8.2. Moment matching using the behavior around zero 146
6.8.3. Improving matrix exponential approximation by matching the behavior around zero 148
6.8.4. Improving matrix exponential approximation by approximating the behavior around zero 150
6.9. Moment bounds of PH(2) distributions 151
6.10. Moment bounds of PH(3) distributions 155
6.10.1. The second and third normalized moments 156
6.10.2. The fourth and fifth normalized moments 157
Chapter 7. Distribution Fitting 165
7.1. Distance measures 166
7.2. Fitting based on maximum likelihood 168
7.2.1. The expectation maximization algorithm 169
7.2.2. Likelihood optimization for acyclic phase type distributions 176
7.3. Fitting based on families of polynomials 179
7.3.1. Bernstein polynomials and Bernstein expolynomials 179
7.3.2. Application of Bernstein expolynomials to distribution fitting 182
7.4. Fitting heavy-tailed distributions 185
7.4.1. Fitting heavy-tailed distributions with monotone decreasing density function 186
7.4.2. Fitting heavy-tailed distributions with possibly non-monotone density function 188
7.5. Continuous versus discrete phase type distributions in practical fitting problems 190
7.5.1. Limit behavior as the scale factor tends to zero 191
7.5.2. The minimum squared coefficient of variation of scaled discrete phase type distributions 192
7.5.3. The optimal scale factor in discrete phase type fitting 194
7.5.4. Approximating non-Markovian models 198
7.5.5. PH and scaled DPH approximation of continuous time models 203
Chapter 8. Simulation 205
8.1. Generating random samples based on the probabilistic interpretation 206
8.1.1. Sub-classes of continuous phase type distributions 206
8.1.2. The play algorithm 207
8.2. Representation transformation to improve the Play method 209
8.2.1. Formulating the optimization problem 210
8.2.2. The solution for acyclic phase type distributions 211
8.2.3. A heuristic representation optimization for general continuous phase type distributions 215
8.3. An acceptance-rejection algorithm 216
8.3.1. Generating random variables from matrix exponential distributions which have a Markovian generator 217
8.3.2. Generating matrix exponential distributed random variables using feedback Erlang blocks 218
8.4. Overview of simulation methods 223
8.5. Numerical examples 224
8.5.1. Optimizing acyclic phase type representations 224
8.5.2. Optimizing general continuous phase type representations 225
Chapter 9. Continuous Phase Type Distribution Based Random Variables 229
9.1. Functions of continuous phase type distributions 229
9.1.1. Bijective functions of PH distributions 230
9.1.2. General functions of PH distributions 230
9.1.3. The considered transformation functions 231
9.2. Multivariate phase type distributions 235
9.2.1. Subset-based multivariate phase type distributions 235
9.2.2. Reward-based multivariate phase type distributions 236
9.2.3. Linear projection based multivariate multivariate phase type distributions 238
Appendices 241
Appendix 1. Description of Related Software Tools 243
Appendix 2. Acronyms 245
References 247
Index 253
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...
