Moment matching algorithm (Chapter 2)

Figure 1.5: Organization of Part I: Analytical tools for multiserver systems.

In Chapter 2, we develop moment matching algorithms, which allow us to map a general probability distribution into a combination of exponential distributions, known as a phase type (PH) distribution. Specifically, a moment matching algorithm maps an input (general) distribution, $G$, into a PH distribution, $P$, such that some moments of $G$ and $P$ agree. For example, if the first moment of $G$ and $P$ agree, then the corresponding random variables have the same mean. If the first two moments of $G$ and $P$ agree, then the corresponding random variables have the same mean and variance. In practice, matching more moments leads to a better approximation. Moment matching algorithms can be evaluated along four different measures:

1. The number of moments matched: In general matching more moments is desirable.
2. The computational efficiency of the algorithm: It is desirable that the algorithm have short running time.
3. The generality of the solution: Ideally the algorithm should work for as broad a class of distributions as possible.
4. The minimality of the number of phases: It is desirable that the matching PH distribution, $P$, have a small number of exponential distributions (phases).

We will provide moment matching algorithms which perform very well along all four of these measures. (i) Our moment matching algorithms match first three moments; (ii) their running time does not depend on the input distribution (we provide closed form solutions for the parameters of the approximate PH distribution); (iii) they apply to the widest possible set of input distributions; (iv) they require a nearly minimal number of phases.

To prove that our moment matching algorithms use a nearly minimal number of phases, we need to know the minimal number of phases needed to approximate (by matching first three moments) an input distribution by a PH distribution. We will therefore start by providing a formal characterization of the set of distributions that are approximated by an $n$-phase PH distribution, for each $n=1,2,3,...$. This characterization is used to prove the minimality of the number of phases used in our moment matching algorithms.