Moment matching algorithm by Bobbio, Horváth, and Telek

In this section, we summarize the recent results by Bobbio et al. [22] on characterization of PH distributions and moment matching algorithms, which build upon our results in Chapter 2. Recall that ${\cal S}^{(n)}$ denotes the set of distributions that are well represented by an $n$-phase acyclic PH distribution (Definition 5). Bobbio et al. provide exact conditions for a distribution $G$ to be in set ${\cal S}^{(n)}$ (see Theorem 21) as well as exact conditions for $G \in {\cal S}^{(n)^*}$ (see Theorem 20), where ${\cal S}^{(n)^*}$ is defined as follows:

Definition 20   Let ${\cal S}^{(n)^*}$ denote the set of distributions that are well-represented by an $n$-phase acyclic PH distribution with no mass probability at zero for positive integer $n$.

Further, Bobbio et al. provide a closed form solution for mapping any $G\in {\cal PH}_3$ to a minimal-phase acyclic PH distribution without mass probability at zero^B.1 (see Theorem 22). As we define the EC distribution and map an input distribution to an EC distribution in Chapter 2, Bobbio et al. also define a subset of PH distributions, and map an input distribution to a PH distribution in the subset. Specifically, Bobbio et al. map an input distribution to an Erlang-Exp distribution (see Figure B.1) or an Exp-Erlang distribution (see Figure B.2).

Figure B.1: The Markov chain whose absorption time defines an Erlang-Exp distribution.

Figure B.2: The Markov chain whose absorption time defines an Exp-Erlang distribution.

Theorem 20   [22] A distribution $G$ is in set ${\cal S}^{(n)^*}$ iff its normalized moments $m_2^G$ and $m_3^G$ satisfy the following conditions:

$$m_2^G \geq \frac{n+1}{n}$$

and

$$\begin{eqnarray*} m_3^G \mbox{ lower bound:} & & \left\{\begin{array}{ll} l... ... & \qquad\mbox{if } \frac{n}{n-1} < m_2^G, \end{array}\right. \end{eqnarray*}$$

where $l_n$ and $u_n$ are defined as follows:

$$\begin{eqnarray*} l_n & = & \frac{(3+a_n)(n-1)+2a_n}{(n-1)(1+a_np_n)} - \frac{2... ...-n-1)\sqrt{1+\frac{n(m_2^G-2)}{n-1}}+(n+2)(3nm_2^G-2n-2)\right) \end{eqnarray*}$$

where

$$\begin{eqnarray*} p_n & = & \frac{(n+1)(m_2^G-2)}{2m_2^G(n-1)} \left(\frac{-2\s... ...c{m_2^G-2}{p_n(1-m_2^G)+\sqrt{p_n^2+\frac{p_nn(m_2^G-2)}{n-1}}} \end{eqnarray*}$$

Theorem 21   [22] A distribution $G$ is in set ${\cal S}^{(n)}$ iff its normalized moments $m_2^G$ and $m_3^G$ satisfy the following conditions:

$$m_2^G \geq \frac{n+1}{n}$$

and

$$\begin{eqnarray*} m_3^G \mbox{ lower bound:} & & \frac{n+2}{n+1} m_2^G \leq m... ...\infty & \mbox{if } \frac{n}{n-1} < m_2^G, \end{array}\right. \end{eqnarray*}$$

where $u_n$ is the same as in Theorem 20.

Theorem 22   [22] Let $G$ be a distribution in ${\cal S}^{(n)^*}\setminus {\cal S}^{(n-1)^*}$. If $m_2^G\leq \frac{n}{n-1}$ or $m_3^G\leq 2m_2^G-1$, then $G$ is well-represented by the Erlang-Exp distribution with the following parameters:

$$\begin{eqnarray*} \lambda_X & = & \frac{ap+1}{\mu_1^G} \\ \lambda_Y & = & \fr... ...2^G)^2(n+1)+16m_3^G(n+1)+m_2^G(n(m_3^G-15)(m_3^G+1)-8(m_3^G+3)) \end{eqnarray*}$$

If $m_2^G > \frac{n}{n-1}$ and $m_3^G > u_{n-1}$, then $G$ is well-represented by the Exp-Erlang distribution with the following parameters:

$$\begin{eqnarray*} \lambda_X & = & \frac{a+p}{\mu_1^G} \\ \lambda_Y & = & \fra... ...frac{2(f-1)(n-1)}{(n-1)(m_2^Gf^2-2f+2)-n} \\ p & = & (f-1)a, \end{eqnarray*}$$

and $f$ is given by the following steps^B.2:

$$\begin{eqnarray*} K_1 & = & n-1 \\ K_2 & = & n-2 \\ K_3 & = & 3m_2^G - 2m_3... ...{15} + K_{17} & \mbox{if } K_{20} < 0. \\ \end{array}\right. \end{eqnarray*}$$