Summary of results

We present three variants of closed form solutions for the free parameters of the EC distribution: the Simple solution, the Complete solution, and the Positive solution. Each of the three solutions achieves slightly different goals. The Simple solution has the advantage of simplicity and readability. For any input distribution $G$, the Complete solution requires the smallest number of phases among the three solutions. The Positive solution achieves an additional property that it does not have mass probability at zero. The Positive solution can be used to construct yet another solution, ZeroMatching, that matches not only matches the first three moments but also the mass probability at zero of the input distribution, as we will discuss in Section 2.9.

Table 2.1 summarizes the characteristics of the three solutions. In all the three solutions, the first three moments of the input distribution are matched, and the parameters of the output EC distribution are provided in closed form. Since the parameters of the solutions are given in closed form, the running time does not depend on the number of necessary number of phases and is bounded by some constant time.

Table 2.1: A summary of three closed form solutions for moment matching.

	Simple	Complete	Positive
number of moments matched	3	3	3
running time	closed form	closed form	closed form
input distributions	almost all ${\cal PH}_3$	all ${\cal PH}_3$	almost all ${\cal PH}_3$
number of phases	$\leq$OPT($G$)+1	$\leq$OPT($G$)+1	$\leq$OPT($G$)+1
possible mass probability at zero	Yes	Yes	No
output distribution	EC	EC	extended EC
solution	Figure 2.11	Figure 2.13	Figure 2.15

To characterize the class of input distributions that are defined for our solutions, we introduce set, ${\cal PH}_3$.

Definition 3   ${\cal PH}_3$ refers to the set of distributions that are well-represented by a PH distribution.

The set ${\cal PH}_3$ is quite broad, and it contains almost all the nonnegative distributions. More precisely,

Proposition 1   Set ${\cal PH}_3$ is dense in the set of all the nonnegative distributions.

The Simple and Positive solutions are defined for almost all the distributions in ${\cal PH}_3$, while the Complete solution is defined for all the distributions in ${\cal PH}_3$. Although the Simple and Positive solutions are not defined for a very small subset in ${\cal PH}_3$, this is not a problem in practice, since a distribution in the small subset can be perturbed to be moved out of the subset^2.1.

To characterize the optimality of the number of phases used in our solutions, we define OPT($G$) as follows:

Definition 4   $OPT(G)$ is defined to be the minimum number of phases in an acyclic PH distribution, allowing a mass probability at zero, that well-represents a distribution $G$.

All of the Simple, Complete, and Positive solutions require at most ${\rm OPT}(G)+1$ phases, but the number of phases in the Complete solution is always at most those in the Simple and Positive solutions. In the definition of OPT($\cdot$), we limit our focus to the set of acyclic PH distributions. A PH distribution is called an acyclic PH distribution if the Markov chain whose absorption time defines the PH distribution does not have a cycle (i.e., any state is never visited more than once). It is not clear whether restricting our search space to the set of acyclic PH distributions is limiting. While it is theoretically possible that the minimum phase solution is cyclic, in practice we have not been able to find a situation where the minimal solution requires cycles.

The Simple and Complete solutions can have mass probability at zero (i.e. $p<1$), but the Positive solution has no mass probability at zero. In some applications, mass probability at zero is not an issue. Such applications include approximating busy period distributions in the analysis of multiserver systems via dimensionality reduction (see Chapter 3) and approximating shortfall distributions in inventory system analysis [197,198]. However, there are also applications where a mass probability at zero increases the computational complexity or even makes the analysis intractable. For example, a PH/PH/1/FCFS queue can be analyzed efficiently via matrix analytic methods (see Section 3.2) when the PH distributions have no mass probability at zero; however, no simple analytical solution is known when the PH distributions have nonzero mass probability at zero.

The key idea in the design of the Positive solution is to match the input distribution by a mixture of an EC distribution (with no mass probability at zero) and an exponential distribution. The use of this type of distribution makes intuitive sense, since it can approximate the EC distribution with mass probability at zero arbitrarily closely by letting the rate of the exponential distribution approach infinity. It turns out, however, that it is not always easy (or even possible) to find a closed form expression for the parameters of the EC distribution and the exponential distribution. We find that in such cases the convolution of an EC distribution and an exponential distribution leads to tractability. We refer to the output distribution of the Positive solution as an extended EC distribution. Figure 2.3 shows the Markov chain whose absorption time defines an extended EC distribution.

Figure 2.3: The Markov chain whose absorption time defines an extended EC distribution.