Computer Science Department
School of Computer Science, Carnegie Mellon University


A Closed-form Solution for Mapping
General Distributions to Minimal PH Distributions

Takayuki Osogami, Mor Harchol-Balter

February 2003

Keywords:Closed form, algorithm, moment matching, Coxian distribution, phase-type distirbution, EC distribution, normalized moment, matrix analytic

Approximating general distributions by phase-type (PH) distributions is a popular technique in queueing analysis, since the Markovian property of PH distributions often allows analytical tractability. This paper proposes an algorithm for mapping a general distribution G to a PH distribution where the goal is to find a PH distribution which matches the first three moments of G. Since efficiency of the algorithm is of primary importance, we first define a particular subset of the PH distributions, which we refer to as EC distributions. The class of EC distributions has very few free parameters, which narrows down the search space, making the algorithm efficient -- In fact we provide a closed-form solution for the parameters of the EC distribution. Our solution is general in that it applies to any distribution whose first three moments can be matched by a PH distribution. Also, our resulting EC distribution requires a nearly minimal number of phases, always within one of the minimal number of phases required by any acyclic PH distribution. Lastly, we discuss numerical stability of our solution.

25 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by