Concluding remarks

In this chapter, moment matching algorithms are proposed. Also, to prove the minimality of the number of phases used in our moment matching algorithms, the set, ${\cal S}^{(n)}$, of distributions that are well-represented by an $n$-phase acyclic phase type (PH) distribution is characterized.

Our moment matching algorithms have broad applicability in computer science, engineering, operations research, etc., where the performance evaluation or optimization in stochastic environment is needed. For example, in this thesis, a moment matching algorithm is used to model a multiserver system as a (multidimensional) Markov chain, as well as in a key step of the analysis of the multidimensional Markov chain via dimensionality reduction. Furthermore, many optimization problems in stochastic environment can be formulated as Markov decision problems [159] by mapping general (input) probability distributions into PH distributions.

Our moment matching algorithms can also be used as a building block to construct a solution with additional properties. For example, the Positive solution can be used as a building block for yet another solution, ZeroMatching, that not only matches the first three moments of the input distribution but also matches the mass probability at zero. Consider a distribution $G$ whose mass probability at zero is $q$. Then, $G$ can be expressed as a mixture of $O$ (the distribution of a random variable $V\equiv 0$) and a distribution $F$ that does not have mass probability at zero. The Positive solution can be used to match the first three moments of $F$ by an extended EC distribution, $E$. Now, a mixture of $O$ and $E$, whose distribution function is $qO(\cdot)+(1-q)E(\cdot)$, matches the first three moments and mass probability at zero of $G$. Observe that the ZeroMatching solution uses at most ${\rm OPT}(G)+1$ phases.

Beyond proving the minimality of the number of phases used in our moment matching algorithms, our characterization of set ${\cal S}^{(n)}$ via set ${\cal T}^{(n)}$ is found to be useful in developing our moment matching algorithms, since the characterization of ${\cal S}^{(n)}$ allows us to determine how close our PH distribution is to the minimal PH distribution, and provides intuition for coming up with improved algorithms. Another benefit of characterizing ${\cal S}^{(n)}$ is that some existing moment matching algorithms, such as Johnson and Taaffe's nonlinear programming approach [90], require knowing the number of phases, $n$, in the minimal PH distribution. The current approach involves simply iterating over all choices for $n$ [90], whereas our characterization would immediately specify $n$.

In developing moment matching algorithms, we have introduced various theoretical concepts such as the normalized moments, $r$-value, sets ${\cal S}^{(n)}$ and ${\cal T}^{(n)}$, function $\phi$, and the EC distribution, and have proved their properties. These new concepts and their properties are found to be quite useful in developing moment matching algorithms, and they have recently stimulated the research in this area.

For example, Bobbio, et al. [22] have recently used the normalized moments to provide exact characterizations of sets ${\cal S}^{(n)}$ and ${\cal S}^{(n)^*}$, where ${\cal S}^{(n)}$ is the set of distributions that can be well-represented by an $n$-phase acyclic PH distribution and ${\cal S}^{(n)^*}$ is the set of distributions that can be well-represented by an $n$-phase acyclic PH distribution with no mass probability at zero. Bobbio, et al. use their exact characterization of ${\cal S}^{(n)}$ to construct a minimal acyclic PH distribution that well-represents any distribution in ${\cal PH}_3$. The PH distributions to which an input distribution is mapped in [22], the Exp-Erlang distribution and the Erlang-Exp distribution, are similar to (but simpler than) the EC (Erlang-Coxian) distribution and the extended EC distribution introduced in this chapter. In fact, the EC distribution is reduced to the Exp-Erlang distribution by setting $p=1$ and $\lambda_{X1}=\lambda_Y$ (see Figure 2.2), and the extended EC distribution is reduced to the Erlang-Exp distribution by setting $\lambda_W=\infty$, $p_X=1$, and $\lambda_{X1}=\lambda_{X2}=\lambda_Y$ (see Figure 2.3). Since the work by Bobbio, et al. builds upon the results in this chapter, we summarize their main results in Appendix B.

In response to increased request, the closed form solutions developed in this chapter have been largely implemented, and the latest implementation of the solutions is made available at an online code repository:

http://www.cs.cmu.edu/~osogami/code/.