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.

• Introduction xiChapter 1 Mathematical Background 11.1. Basic properties of random variables 11.2. Moments of random variables and related quantities 21.3. Laplace transformation 31.4. z transform 41.5. Matrix functions of quadratic matrices 51.6. Matrix inverse 51.7. Eigenvalues and the characteristic polynomial 51.8. Spectral decomposition 61.9. Ordinary differential equation of vector functions 101.10. Exponential distribution 111.11. Erlang distribution 121.12. Discrete time Markov chain 121.13. Continuous time Markov chain 141.14. Kronecker algebra 15Chapter 2. Continuous Phase Type Distributions 192.1. Definition and basic properties 192.2 Stochastic meaning of (-A)-1232.3. Rational Laplace transform 242.4. Decomposition of matrix exponential functions 262.5. Similarity transformation 302.5.1. Similarity transformation with identical sizes 302.5.2. Similarity transformation with different sizes 312.5.3. Full rank representation 322.6. Closure properties 322.7 Positive density on (0, 1) 342.8. Eigenvalue structure 352.9. Steepest increase property 39Chapter 3. Discrete Phase Type Distributions 433.1. Definition and basic properties 433.2 Stochastic meaning of (I-B)-1 453.3. Rational z transform function 463.4. Decomposition of the matrix geometric function 463.5. Similarity transformations 483.6. Closure properties 483.7. Eigenvalue structure 49Chapter 4. Matrix Exponential and Matrix Geometric Distributions 514.1. Matrix exponential distributions 514.1.1. Non-negative matrix exponential subclasses 534.2. Matrix geometric distributions 54Chapter 5. Classes and Representations of Continuous Phase Type Distributions 575.1. Number of parameters 575.2. Representations of continuous phase type distributions 585.2.1. Matrix representation 585.2.2. Markovian representation 585.2.3. Laplace representation 595.2.4. Moment representation 595.3. Transformations between continuous phase type representations 605.3.1. From matrix and Markovian representations to Laplace and moment representations 605.3.2. From Laplace representation to moment representation 605.3.3. From moment representation to matrix representation 605.3.4. From Laplace representation to matrix representation 615.3.5. From matrix representation to Markovian representation 615.4. Properties of the matrix representation of PH(n) distributions 625.4.1. 2n-1 versus n2 + n-1 parameters 625.4.2. Different matrix representations 635.5. Subclasses of continuous phase type distributions 655.5.1. Subclasses with real eigenvalues 655.5.2. Subclasses with complex eigenvalues 735.6. Canonical Markovian representation 765.7. Analysis of a non-Markovian representation 775.7.1. Monocyclic representation 815.7.2. Transformation to a Markovian representation 825.8. Representation minimization 855.8.1. Numerical issues 865.9. Markovian representation minimization 86Chapter 6. Moment Matching 896.1. Continuous phase type distributions with minimal squared coefficient of variation 896.2. Moment bounds of continuous phase type distributions based on the steepest increase property 966.3. Matrix exponential distributions with minimal squared coefficient of variation 996.3.1. Matrix exponential distributions with complex eigenvalues 996.3.2. Matrix exponential distributions with real eigenvalues 1046.4. Characteristics of moments of continuous phase type and matrix exponential distributions 1076.5. Matching 2n-1 moments with size n matrix representations 1146.5.1. Padé approximation for continuous distributions 1146.5.2. Padé approximation for discrete distributions 1186.6. Matching any three moments with minimal acyclic phase type distributions 1206.6.1. Moment bounds 1216.6.2. Explicit moment matching with minimal number of parameters 1266.6.3. Proof of theorem 6.28 1306.6.4. Proof of theorem 6.29 1366.7. Matching any valid odd number of moments with generalized hyper-Erlang distributions 1376.7.1. Moment matching procedure for generalized hyper-Erlang distributions 1376.7.2. Numerical examples 1406.8. Matching probability density function at zero 1456.8.1. Numerical examples 1466.8.2. Moment matching using the behavior around zero 1466.8.3. Improving matrix exponential approximation by matching the behavior around zero 1486.8.4. Improving matrix exponential approximation by approximating the behavior around zero 1506.9. Moment bounds of PH(2) distributions 1516.10. Moment bounds of PH(3) distributions 1556.10.1. The second and third normalized moments 1566.10.2. The fourth and fifth normalized moments 157Chapter 7. Distribution Fitting 1657.1. Distance measures 1667.2. Fitting based on maximum likelihood 1687.2.1. The expectation maximization algorithm 1697.2.2. Likelihood optimization for acyclic phase type distributions 1767.3. Fitting based on families of polynomials 1797.3.1. Bernstein polynomials and Bernstein expolynomials 1797.3.2. Application of Bernstein expolynomials to distribution fitting 1827.4. Fitting heavy-tailed distributions 1857.4.1. Fitting heavy-tailed distributions with monotone decreasing density function 1867.4.2. Fitting heavy-tailed distributions with possibly non-monotone density function 1887.5. Continuous versus discrete phase type distributions in practical fitting problems 1907.5.1. Limit behavior as the scale factor tends to zero 1917.5.2. The minimum squared coefficient of variation of scaled discrete phase type distributions 1927.5.3. The optimal scale factor in discrete phase type fitting 1947.5.4. Approximating non-Markovian models 1987.5.5. PH and scaled DPH approximation of continuous time models 203Chapter 8. Simulation 2058.1. Generating random samples based on the probabilistic interpretation 2068.1.1. Sub-classes of continuous phase type distributions 2068.1.2. The play algorithm 2078.2. Representation transformation to improve the Play method 2098.2.1. Formulating the optimization problem 2108.2.2. The solution for acyclic phase type distributions 2118.2.3. A heuristic representation optimization for general continuous phase type distributions 2158.3. An acceptance-rejection algorithm 2168.3.1. Generating random variables from matrix exponential distributions which have a Markovian generator 2178.3.2. Generating matrix exponential distributed random variables using feedback Erlang blocks 2188.4. Overview of simulation methods 2238.5. Numerical examples 2248.5.1. Optimizing acyclic phase type representations 2248.5.2. Optimizing general continuous phase type representations 225Chapter 9. Continuous Phase Type Distribution Based Random Variables 2299.1. Functions of continuous phase type distributions 2299.1.1. Bijective functions of PH distributions 2309.1.2. General functions of PH distributions 2309.1.3. The considered transformation functions 2319.2. Multivariate phase type distributions 2359.2.1. Subset-based multivariate phase type distributions 2359.2.2. Reward-based multivariate phase type distributions 2369.2.3. Linear projection based multivariate multivariate phase type distributions 238Appendices 241Appendix 1. Description of Related Software Tools 243Appendix 2. Acronyms 245References 247Index 253