Moment matching algorithm

How can we map a general distribution into a combination of exponential distributions?

Much of queueing theory revolves around the exponential distribution, since the memoryless nature of the exponential distribution enables an analysis via Markov chains. Unfortunately, real-world workloads such as CPU service requirements, file sizes, durations of FTP transfers, etc. do not have exponential distributions, but rather follow various general distributions. A way for us to deal with workloads with general distributions is to model these general distributions by a combination of exponential distributions, known as a phase type (PH) distribution, first introduced by M. F. Neuts [133,136]. The PH distribution then fits nicely into the Markov chain.

A popular approach in mapping a general probability distribution, $G$, into a phase type (PH) distribution, $P$, is to choose $P$ such that some moments of $P$ and $G$ agree. Matching the first moment of any nonnegative distribution is possible by a single exponential distribution. Matching the first moment is certainly important, but unfortunately it is often not sufficient, as ignoring the higher moments can result in misleading conclusions.

Thus, it is desirable to match more moments of the input distribution $G$ by $P$. Matching more moments may be possible if we are allowed to use many exponential distributions (phases). However, the use of many phases in the PH distribution increases the complexity of the Markov chain, and makes its analysis hard. Matching many moments using a small number of phases may be possible if we are allowed to use unbounded computational resources or if we limit the class of input distributions. However, these limitations are not desirable. Achieving all the four desirable properties is the challenge in designing a moment matching algorithm:

1. It is desirable that more moments of the input distribution, $G$, and the matching PH distribution, $P$, agree.
2. It is desirable that $P$ have a small number of phases.
3. It is desirable that the algorithm be defined for a broad class of input distributions.
4. It is desirable that the algorithm have short running time.