Minimal-Norm Phase-Type Representations and the Minimal Maier Parameter Beyond Order Two

A phase-type (PH) distribution — the law of the time until absorption in a finite continuous-time Markov chain — carries an intrinsic analytic scale: the minimal Maier parameter, i.e. the smallest $c$ such that all derivatives of $e^{cx}f(x)$ at the origin are nonnegative, equivalently the smallest common scale parameter of an Erlang-mixture representation of the law. Any Markovian representation $\mathrm{PH}(\boldsymbol\alpha,A)$ certifies the property at $c$ equal to the maximal absolute entry of $A$, so the minimal representable entry norm $m(F)$ always satisfies $m(F)\ge\bar c(F)$. Sangüesa (2010) resolved order two completely, computing $\bar c$ in closed form from the poles and constructing explicit $2\times2$ representations with $\|A\|=\bar c$ exactly, and proved a sharp pole-based lower bound; extensions to higher orders are explicitly left open, including O'Cinneide's Conjecture 6 on an absolute constant $\Delta$ with $m(F)\le\Delta\,\bar c(F)$ uniformly over all phase-type distributions. The problem — whether $m(F)=\bar c(F)$ is attained for every PH law, whether a uniform $\Delta$ exists, and the exact pole-dependence of $\bar c$ in order $\ge3$ — remains open.

Background

A phase-type (PH) distribution is the law of the time until absorption in a finite-state continuous-time Markov chain with a single absorbing state. Concretely, a distribution $F$ on $[0,\infty)$ is PH with representation $\mathrm{PH}(\boldsymbol\alpha,A)$ of order $n$ when $\boldsymbol\alpha$ is a row vector of nonnegative starting probabilities summing to at most one and $A$ is an $n\times n$ sub-intensity matrix (negative diagonal entries, nonnegative off-diagonal entries, nonpositive row sums), with $F(x)=1-\boldsymbol\alpha e^{xA}\mathbf 1,\qquad x\ge 0,$ where $\mathbf 1$ is the all-ones column; the order is the number of transient states. PH distributions are dense (for weak convergence) among distributions on $[0,\infty)$ and are the standard modeling class of matrix-analytic queueing, reliability and risk theory because they combine Markovian structure with rational Laplace–Stieltjes transforms (LSTs). Dropping the sign constraints in the density formula $f(x)=\boldsymbol\alpha e^{xA}\mathbf t$ yields the larger class of matrix-exponential (ME) distributions, i.e. the absolutely continuous laws on $[0,\infty)$ with rational LST (see Bean, Fackrell and Taylor 2008). O'Cinneide (1990) characterized the PH subclass inside ME: an absolutely continuous law on $[0,\infty)$ is PH if and only if its density is strictly positive and continuous on $(0,\infty)$ and its LST is rational with a unique pole of maximal real part.

Maier (1991), in an algebraic construction of PH distributions (p. 591), proved the following property of the density $f$ of an absolutely continuous PH law: there exists $c>0$ such that $d_n(c):=\left.\frac{d^n}{dx^n}\big(e^{cx}f(x)\big)\right|_{x=0}\ge 0\qquad\text{for all } n\ge 1,$ now called Maier's property. Since $e^{cx}f(x)=\sum_{n\ge0}d_n(c)\,x^n/n!$, the property says precisely that $f$ is the exponential tilt of a power series with nonnegative coefficients, and it is equivalent to writing $F$ as a mixture of Erlang densities sharing the common scale parameter $c$ (the Erlang$(c,n)$ density is $c^n x^{n-1}e^{-cx}/(n-1)!$). The minimal admissible value $\bar c(F)=\inf\{c>0:\ d_n(c)\ge0\ \text{for all } n\ge1\}$ is thus an intrinsic analytic scale of $F$ — the smallest common scale parameter of an Erlang-mixture representation — and it controls the uniform error constants of gamma/Erlang-type approximations of $F$ (Sangüesa 2010, Bernoulli), which is the applied motive for making $c$ as small as possible.

The link to representations is the crux of the question. Writing $\mathbf t=-A\mathbf 1\ge0$ for the exit-rate vector, one has $e^{cx}f(x)=\boldsymbol\alpha e^{x(cI+A)}\mathbf t$, so $d_n(c)=\boldsymbol\alpha(cI+A)^n\mathbf t$. If $c=\|A\|$, the maximum absolute entry of $A$, then $cI+A$ is entrywise nonnegative, whence $d_n(\|A\|)\ge0$: every representation certifies Maier's property at $c=\|A\|$ (O'Cinneide 1999, p. 751). Representations of a fixed PH law are highly non-unique — across orders and across similarity transforms that may or may not preserve the Markovian sign pattern — and even canonical-form equivalences are delicate: He and Zhang (2005) showed that not every PH representation admits an equivalent unicyclic representation (one whose state-transition graph contains a single directed cycle) of the same order. Defining $m(F)=\inf\{\|A\|:\ F=\mathrm{PH}(\boldsymbol\alpha,A)\ \text{for some admissible }\boldsymbol\alpha\},$ one therefore always has $\bar c(F)\le m(F)$, but a priori the minimal representable norm can exceed the analytic threshold. O'Cinneide's 1999 open-problems survey (Conjecture 6) connects the two quantities; in the uniform-constant form it asks whether some absolute $\Delta<\infty$ satisfies $m(F)\le\Delta\,\bar c(F)$ for every PH distribution, with $\Delta$ independent of order and parameters.

Sangüesa (2010, Stochastic Models 26(1):124–140) settled order two completely. A phase-type law of order two (PH(2)) has one of two canonical density forms: either a linear combination of two distinct exponential densities, $f(x)=\alpha\beta_1e^{-\beta_1x}+(1-\alpha)\beta_2e^{-\beta_2x}$ with $0<\beta_1<\beta_2$ and $0\le\alpha\le\beta_2/(\beta_2-\beta_1)$, $\alpha\ne1$ — the range in which the combination is a nonnegative density, and note that the upper bound exceeds one — or a mixture of an exponential and an Erlang(2) density (the law of the sum of two independent exponential variables) sharing a common scale parameter $\beta$ (Bodrog, Heindl, Horváth and Telek 2008). For the two-exponential form she computed, in closed form, $\bar c=\begin{cases}\dfrac{\alpha\beta_1^2+(1-\alpha)\beta_2^2}{\alpha\beta_1+(1-\alpha)\beta_2}, & 0<\alpha<\dfrac{\beta_2}{\beta_1+\beta_2},\\ \dfrac{\beta_1+\beta_2}{2}, & \dfrac{\beta_2}{\beta_1+\beta_2}\le\alpha\le\dfrac{\beta_2}{\beta_2-\beta_1},\ \alpha\ne1,\end{cases}$ and for the exponential–Erlang(2) form one has $\bar c=\beta$; in both cases she constructed explicit $2\times2$ sub-intensity matrices with $\|A\|=\bar c$ exactly, so $m(F)=\bar c(F)$ for every PH(2) law. She also proved a sharp pole-based lower bound valid at every order: writing the distinct poles of the LST as $p_j=-\phi_j+i\theta_j$ ($\phi_j>0$, $\theta_j\ge0$, $\phi_j\ge\phi_1$), with $-\phi_1$ the unique pole of maximal real part, $\bar c\ \ge\ c^*=\max_{j\ge2}\Big\{\frac{\phi_j+\phi_1}{2}+\frac{\theta_j^2}{2(\phi_j-\phi_1)}\Big\}$ (the maximum runs over the remaining distinct poles, one representative per complex-conjugate pair, and $c^*=\phi_1$ when there is a single distinct pole), which strengthens an earlier estimate $\bar c\ge\phi_1/2$ to $\bar c\ge\phi_1$; and she showed that Maier's property characterizes PH inside the ME class. She states explicitly that extensions to higher orders appear difficult.

Problem Statement

Let $F$ be an absolutely continuous phase-type distribution with density $f$. Define $d_n(c)=\left.\frac{d^n}{dx^n}\big(e^{cx}f(x)\big)\right|_{x=0},\qquad \bar c(F)=\inf\{c>0:\ d_n(c)\ge0\ \forall n\ge1\},$ and $m(F)=\inf\{\|A\|:\ F=\mathrm{PH}(\boldsymbol\alpha,A)\ \text{for some row vector }\boldsymbol\alpha\ge0\text{ with }\boldsymbol\alpha\mathbf 1\le1\},$ where $\|A\|=\max_{i,j}|A_{ij}|$ is the entrywise maximum norm, $\mathrm{PH}(\boldsymbol\alpha,A)$ is a Markovian representation with sub-intensity matrix $A$, and the infimum runs over all such representations of all finite orders. Every representation satisfies $\|A\|\ge\bar c(F)$, and for every phase-type law of order two one has $m(F)=\bar c(F)$ with explicitly constructible representations (Sangüesa 2010). The open problem left by the source paper is the determination of $m(F)/\bar c(F)$ across the whole PH class, in three coordinated parts:

(1) Exact minimal-norm phenomenon beyond order two: does every phase-type distribution of order greater than two — that is, every law admitting no representation with a $2\times2$ sub-intensity matrix — admit a Markovian representation with $\|A\|=\bar c(F)$?

(2) Uniform constant (O'Cinneide's Conjecture 6): does there exist an absolute constant $\Delta<\infty$, independent of the order, the parameters, and the distribution, such that $m(F)\le\Delta\,\bar c(F)$ for every phase-type distribution $F$?

(3) Pole-structural analysis: determine $\bar c(F)$ exactly for higher-order laws from the poles $p_j=-\phi_j+i\theta_j$ of the Laplace–Stieltjes transform (LST), where $\phi_j>0$, $\theta_j\ge0$ and $-\phi_1$ is the unique pole of maximal real part, together with the leading partial-fraction coefficients — in particular, determine when the sharp lower bound $c^*=\max_{j\ge2}\Big\{\frac{\phi_j+\phi_1}{2}+\frac{\theta_j^2}{2(\phi_j-\phi_1)}\Big\}$ (the maximum over all distinct poles other than $-\phi_1$, one representative per complex-conjugate pair; $c^*=\phi_1$ when there is a single distinct pole) is attained, and how large the gap $\bar c-c^*$ can be; this analytic computation underpins any quantitative answer to (1) or (2).

The problem is completely settled by a proof that equality holds in (1) for all orders; by a proof of a uniform bound in (2) with an explicit $\Delta$; or by a refutation of either statement through an explicit phase-type law, or explicit family of laws, whose certified ratio $m(F)/\bar c(F)$ violates it. Part (3) is supporting analysis for (1) and (2): its resolution contributes to a quantitative answer but is not by itself one of the settling outcomes above.

References

1. Sangüesa, C. (2010). On the Minimal Value in Maier's Property Concerning Phase-Type Distributions. Stochastic Models 26(1), 124–140. DOI: 10.1080/15326340903517139. https://doi.org/10.1080/15326340903517139 (source paper)
2. Maier, R. S. (1991). The algebraic construction of phase-type distributions. Communications in Statistics. Stochastic Models 7(4), 573–602. DOI: 10.1080/15326349108807207. https://doi.org/10.1080/15326349108807207
3. O'Cinneide, C. A. (1999). Phase-type distributions: open problems and a few properties. Communications in Statistics. Stochastic Models 15(4), 731–757. DOI: 10.1080/15326349908807560. https://doi.org/10.1080/15326349908807560
4. Sangüesa, C. (2010). Uniform error bounds for a continuous approximation of non-negative random variables. Bernoulli 16(2), 561–584. DOI: 10.3150/09-BEJ209. https://doi.org/10.3150/09-BEJ209
5. O'Cinneide, C. A. (1990). Characterization of phase-type distributions. Communications in Statistics. Stochastic Models 6(1), 1–57. DOI: 10.1080/15326349908807134. https://doi.org/10.1080/15326349908807134
6. Bean, N. G., Fackrell, M., Taylor, P. (2008). Characterization of Matrix-Exponential Distributions. Stochastic Models 24(3), 339–363. DOI: 10.1080/15326340802232186. https://doi.org/10.1080/15326340802232186
7. Bodrog, L., Heindl, A., Horváth, G., Telek, M. (2008). A Markovian canonical form of second-order matrix-exponential processes. European Journal of Operational Research 190(2), 459–477. DOI: 10.1016/j.ejor.2007.06.020. https://doi.org/10.1016/j.ejor.2007.06.020
8. He, Q.-M., Zhang, H. (2005). A Note on Unicyclic Representations of Phase Type Distributions. Stochastic Models 21(2–3), 465–483. DOI: 10.1081/STM-200057131. https://doi.org/10.1081/STM-200057131
9. Commault, C., Mocanu, S. (2003). Phase-type distributions and representations: some results and open problems for system theory. International Journal of Control 76(6), 566–580. DOI: 10.1080/0020717031000114986. https://doi.org/10.1080/0020717031000114986
10. He, Q.-M., Zhang, H., Vera, J. C. (2013). Majorization and Extremal PH Distributions. In: Latouche, G., et al. (eds.), Matrix-Analytic Methods in Stochastic Models. Springer Proceedings in Mathematics & Statistics, vol. 27, 107–121. Springer, New York. DOI: 10.1007/978-1-4614-4909-6_6. https://doi.org/10.1007/978-1-4614-4909-6_6
11. He, Q.-M. (2014). From the Exponential Distribution to Phase-Type Distributions. In: Fundamentals of Matrix-Analytic Methods. Springer, New York, 1–83. DOI: 10.1007/978-1-4614-7330-5_1. https://doi.org/10.1007/978-1-4614-7330-5_1
12. Horváth, G., Reinecke, P., Telek, M., Wolter, K. (2016). Heuristic representation optimization for efficient generation of PH-distributed random variates. Annals of Operations Research 239(2), 643–665. DOI: 10.1007/s10479-014-1736-x. https://doi.org/10.1007/s10479-014-1736-x
13. Liu, Y., Yao, D., Zhang, H. (2025). A non-convex optimization approach of searching algebraic degree phase-type representations for general phase-type distributions. Advances in Applied Probability 57(3), 1101–1137. DOI: 10.1017/apr.2024.72. https://doi.org/10.1017/apr.2024.72