Moment matching algorithms

Prior work has contributed a large number of moment matching algorithms. While all of these algorithms excel with respect to some of the four measures mentioned earlier (number of moments matched; minimality of the number of phases; generality of the solution; computational efficiency of the algorithm), they all are deficient in at least one of these measures as explained below.

In cases where matching only two moments suffices, it is possible to achieve solutions which perform very well along all the other three measures. Sauer and Chandy [171] provide a closed form solution for matching two moments of a general distribution with squared coefficient of variation $C^2>0$ (i.e., any distribution in ${\cal PH}_3$). They use a two-phase hyper-exponential distribution, H$_2$, for matching distributions with squared coefficient of variability $C^2 > 1$, and a generalized Erlang distribution for matching distributions with $C^2<1$. Marie [122] provides a closed form solution for matching two moments of a general distribution with $C^2>0$. He uses a two-phase Coxian$^+$ PH distribution for distributions with $C^2 > 1$, and a generalized Erlang distribution for distributions with $C^2<1$.

If one is willing to match only a subset of distributions, then again it is possible to achieve solutions which perform very well along the remaining three measures. Whitt [200] and Altiok [6] focus on the set of distributions with $C^2 > 1$ and sufficiently high third moment. They obtain a closed form solution for matching three moments of any distribution in this set. Whitt matches to an H$_2$, and Altiok matches to a two-phase Coxian$^+$ PH distribution. Telek and Heindl [190] focus on the set of distributions with $C^2\geq \frac{1}{2}$ and various constraints on the third moment. They obtain a closed form solution for matching three moments of any distribution in this set, by using a two-phase acyclic PH distribution with no mass probability at zero.

Johnson and Taaffe [87,88] come closest to achieving all four measures. They provide a closed form solution for matching the first three moments of any distribution $G\in {\cal PH}_3$. They use a mixed Erlang distribution with common order. Unfortunately, this mixed Erlang distribution requires $2{\rm OPT}(G)+2$ phases in the worst case.

In complementary work, Johnson and Taaffe [89,90] again look at the problem of matching the first three moments of any distribution $G\in {\cal PH}_3$, this time using three types of PH distributions: a mixture of Erlang distributions, a Coxian$^+$ PH distribution, and a general PH distribution. Their solution is nearly minimal in that it requires at most ${\rm OPT}(G)+2$ phases. Unfortunately, their algorithm requires solving a nonlinear programming problem and hence is computationally inefficient, requiring time exponential in ${\rm OPT}(G)$.

Above we have described the prior work focusing on moment matching algorithms, which is the focus of this chapter. There is also a large body of work focusing on fitting the shape of an input distribution using a PH distribution. Recent research has looked at fitting heavy-tailed distributions to PH distributions [55,76,77,98,162,187]. There is also work which combines the goals of moment matching with the goal of fitting the shape of the distribution [86,173]. The work above is clearly broader in its goals than simply matching three moments. Unfortunately there is a tradeoff: obtaining a more precise fit requires more phases, and it can sometimes be computationally inefficient [86,173].