Key idea

The general approach in designing moment matching algorithms in the literature is to start by defining a subset ${\cal S}$ of the PH distributions, and then map each input distribution $G$ into a distribution in ${\cal S}$. The reason for limiting the solution to a distribution in ${\cal S}$ is that this narrows the search space and thus improves the computational efficiency of the algorithm. One has to be careful in defining the subset ${\cal S}$, however. If ${\cal S}$ is too small, it may exclude solutions with a minimal number of phases. Also, if ${\cal S}$ is too small, it may limit the class of input distributions, or it may limit the number of moments that can be matched.

The key idea in our moment matching algorithm is the way that we define the subset, ${\cal S}$, of PH distributions, which we call EC (Erlang-Coxian) distributions. The EC distribution has only six free parameters, regardless of the number of phases, which allows us to derive a closed form solution for these parameters in terms of the moments of the input distribution. This is in contrast to the general PH distribution, as an $n$-phase PH distribution has $\Theta(n^2)$ free parameters. Furthermore, the class of EC distributions is broad enough to excel in the other three desired properties. In particular, the EC distribution allows us to match the first three moments of the input distribution, and it applies to the broadest possible class of input distributions (almost all nonnegative distributions). Also, the number of phases used in the output EC distribution is nearly minimal. Below, we say that distribution $G$ is well-represented by $P$ if $P$ and $G$ agree on their first three moments.

Definition 1   A distribution $G$ is well-represented by a distribution $F$ if $F$ and $G$ agree on their first three moments.

Figure 2.2 shows the Markov chain whose absorption time defines an $n$-phase EC distribution. Here, at time zero, the Markov chain is in state 1 with probability $p$ and in the absorbing state with probability $1-p$. If the absorbing state is the initial state, the absorption time is zero. When the Markov chain is in state $i$, it stays in the state for a random time having an exponential distribution with rate $\lambda_Y$, and then transitions to state $i+1$, for $1\leq i\leq n-2$. (The time it takes to transition from state 1 to state $n-1$ is said to have an Erlang-($n-2$) distribution or an $(n-2)$-phase Erlang distribution, $E_{n-2}$). When the Markov chain is in state $n-1$, it stays in the state for a random time having an exponential distribution with rate $\lambda_{X1}$, and then transitions to state $n$ with probability $p_X$ and to the absorbing state with probability $1-p_X$. When the Markov chain is in state $n$, it stays in the state for a random time having an exponential distribution with rate $\lambda_{X2}$, and then transitions to the absorbing state. (The time it takes to transition from state $n-1$ to the absorbing state is said to have a two-phase Coxian$^+$ PH distribution (as we will define in Section 2.2).) The time until the Markov chain enters the absorbing state is said to have an $n$-phase EC distribution.

Definition 2   An $n$-phase EC (Erlang-Coxian) distribution is the convolution of an $(n-2)$-phase Erlang distribution and a two-phase Coxian$^+$ distribution, where the EC distribution may have mass probability at zero.

Figure 2.2: The Markov chain whose absorption time defines an $n$-phase EC distribution. The first box above depicts the Markov chain that defines an Erlang-$(n-2)$ distribution, and the second box depicts the Markov chain that defines a two-phase Coxian$^+$ PH distribution.

We now provide some intuition behind the creation of the EC distribution. We will see that a Coxian$^+$ PH distribution is very good for approximating a distribution with high variability. In particular, we will see that a two-phase Coxian$^+$ PH distribution can well-represent any distribution that has high second and third moments. However, we will also see that a Coxian$^+$ PH distribution requires many more phases for approximating distributions with lower second and third moments. The large number of phases needed implies that many free parameters must be determined, implying high computational cost to yield an exact (optimal) solution. By contrast, an $n$-phase Erlang distribution has only two free parameters and is also known to have the least variability among all the $n$-phase PH distributions [5,142]. As we will see, however, the Erlang distribution is limited in the set of distributions which it can well-represent.

By combining the Erlang distribution with the two-phase Coxian$^+$ PH distribution, we can represent distributions with all ranges of variability, while using only a small number of phases. Furthermore, the fact that the EC distribution has a small number of parameters, ($n$, $p$, $\lambda_Y$, $\lambda_{X1}$, $\lambda_{X2}$, $p_X$), allows us to obtain closed form expressions for these parameters that well-represent any given distribution in $\cal{PH}_3$.