A computable upper bound on the triangular order of phase-type distributions with real poles

The algorithm of He and Zhang (2008) computes minimal ordered Coxian representations of phase-type (PH) distributions whose Laplace–Stieltjes transform has only real poles by testing, order by order, derivative-based necessary and sufficient conditions through a nonlinear program, starting upward from a computable lower bound. The search stops at the first feasible order, but no a priori computable upper bound on the triangular order — the minimal number of phases over all ordered Coxian representations — is known beyond existence guarantees, and it is conjectured that the triangular orders of distributions sharing a fixed generator are unbounded. The open problem is to establish an explicit, provably correct upper bound on the triangular order computable from a given representation or its transform (equivalently, an order-computing algorithm with a proven termination bound). Such results would turn the incremental per-order search into a single finite program and bound the computational effort of computing minimal Coxian representations.

Background

A phase-type (PH) distribution is the distribution of the time until a finite-state continuous-time Markov chain with one absorbing state reaches absorption, all other states being transient. Writing $\boldsymbol{\alpha}$ for the row vector of initial probabilities over the transient states and $T$ for the subgenerator (the transient block of the infinitesimal generator, with negative diagonal and nonnegative off-diagonal entries), the pair $(\boldsymbol{\alpha},T)$ is a PH representation and its number of transient states is the order of the representation. PH distributions are dense among distributions on $[0,\infty)$ and underpin the matrix-analytic methodology of queueing, reliability, and risk theory, where the cost of evaluating performance measures grows with the number of phases; representations with fewer phases are therefore of direct computational value. Representations are highly non-unique, and the order of a PH distribution is the minimum order over all of its PH representations.

The Laplace–Stieltjes transform (LST) of a PH distribution is a rational function; written in lowest terms, the degree of its denominator is a distributional invariant called the algebraic degree, and every representation must have order at least the algebraic degree (Commault and Chemla, 1996). Commault and Chemla also proved that when the numerator has degree at most one and all poles are real, the order equals the algebraic degree; outside this case the order can be dramatically larger than the algebraic degree, and computing it is the core difficulty of the minimal representation problem, which the surveys of O'Cinneide (1999) and Commault and Mocanu (2003) list among the open problems of the area.

Among structured subclasses, a Coxian distribution is one whose subgenerator is bi-diagonal, so the underlying chain visits its states in a fixed sequence before absorption; an ordered Coxian representation additionally has absorption rates that decrease along the sequence. Cumani (1982) showed that any acyclic PH representation of order $n$ can be rewritten as a Coxian representation of order $n$, so no blow-up in the number of phases occurs inside the acyclic class. For general, possibly cyclic representations the situation changes: O'Cinneide (1991), through polytopes of initial vectors that are invariant under the residual-life transformation and that control which pole structures a representation can realize, proved that a PH distribution whose LST has only real poles always possesses a triangular representation — but his existence argument yields no bound on the order of the representation it guarantees. The minimal number of phases over all ordered Coxian representations of such a distribution is called its triangular order, in the usage of He and Zhang (2008, 2009); O'Cinneide (1993) introduced the term for triangular phase-type representations, and the two minima are not known to coincide.

He and Zhang (2006a, 2006b) turned this existence theory into spectral polynomial algorithms that compute bi-diagonal representations, and He and Zhang (2008) gave the first algorithm computing minimal ordered Coxian representations. They characterized, by necessary and sufficient conditions, when an ordered Coxian representation of a given order exists and is minimal: the conditions are expressed through the derivatives of the distribution function $F$ at zero, organized in a recursion that combines the candidate rates with the values $F^{(i)}(0)$ and requires the resulting coefficients to be nonnegative. Candidate orders $n$ are then tested by a nonlinear program (a constrained nonlinear optimization problem) starting upward from the computable lower bound $N^*=\max\{N_m,\lceil 1/\mathrm{cv}^2\rceil\}$, where $N_m$ is the algebraic degree and $\mathrm{cv}$ the coefficient of variation; the second term uses the consequence $n\ge 1/\mathrm{cv}^2$ of the theorem of Aldous and Shepp (1987) that the Erlang distribution is the least variable order-$n$ PH distribution, in sharp form $\mathrm{cv}\ge 1/\sqrt{n}$ for every order-$n$ PH distribution. The search is guaranteed to stop only in the sense that it halts at the first feasible order: since no computable upper bound on the triangular order is known, the computational effort cannot be bounded in advance, and a conjecture current in this literature holds that the triangular order of distributions with a fixed generator can be arbitrarily large.

The gap is concrete rather than hypothetical. In the examples of He and Zhang (2008), one order-3 cyclic generator gives distributions whose triangular orders equal $4,5,6,8,12,$ and $31$ along a one-parameter family of initial vectors approaching the boundary of the relevant invariant polytope, and a minimal ordered Coxian representation may require rates that are not eigenvalues of the original generator, so spectral data alone cannot delimit the search space. The question is the nonnegative counterpart of the classical minimal realization problem of linear systems theory, where the positivity constraint on the matrices is precisely what makes order reduction difficult (Commault and Mocanu, 2003).

Problem Statement

Let $F$ be a phase-type distribution given by a PH representation $(\boldsymbol{\alpha},T)$ of finite order (cyclic representations allowed) whose Laplace–Stieltjes transform has only real poles; let its triangular order be the minimal number of phases over all ordered Coxian representations of $F$. By O'Cinneide's existence theorem this number is finite, and by the characterization of He and Zhang (2008) it is computable by searching orders $n=N^*,N^*+1,N^*+2,\ldots$ upward from the computable lower bound $N^*$ and stopping at the first order whose derivative-based feasibility conditions hold — but no a priori computable upper bound on it is known, so the effort of this search cannot be bounded in advance. Resolve the effective boundedness of the triangular order, in either of the following equivalent forms: (i) an explicitly computable function $B$ of the representation data $(\boldsymbol{\alpha},T)$ — or of the coefficients of the Laplace–Stieltjes transform — together with a proof that the triangular order of every real-poled PH distribution is at most $B$, where $B$ is computed by a finite procedure that does not itself require executing the per-order minimality search; or (ii) an algorithm that takes any real-poled PH representation and returns its triangular order with a proven termination bound on all inputs. A related conjecture in this literature holds that, for a fixed PH generator with only real eigenvalues, the triangular orders of its distributions are unbounded; settling that conjecture, in either direction, would not by itself resolve this problem, although an affirmative settlement would show that any valid bound must depend on the initial vector and not on the generator or its spectrum alone. The restriction to transforms with only real poles is intrinsic to the question rather than a narrowing: outside this class a Coxian representation need not exist.

References

1. Qi-Ming He and Hanqin Zhang, "An Algorithm for Computing Minimal Coxian Representations", INFORMS Journal on Computing 20(2):179–190, 2008. DOI: 10.1287/ijoc.1070.0228, https://doi.org/10.1287/ijoc.1070.0228
2. Yujie Liu, Dacheng Yao, and Hanqin Zhang, "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, 2025. DOI: 10.1017/apr.2024.72, https://doi.org/10.1017/apr.2024.72; preprint arXiv:2409.12673, https://arxiv.org/abs/2409.12673
3. Yujie Liu, Dacheng Yao, and Hanqin Zhang, "On Substochastic Inverse Eigenvalue Problems with the Corresponding Eigenvector Constraints", SIAM Journal on Matrix Analysis and Applications 45(3):1689–1719, 2024. DOI: 10.1137/23M1547305, https://doi.org/10.1137/23M1547305; preprint arXiv:2409.09034, https://arxiv.org/abs/2409.09034
4. Colm Art O'Cinneide, "Phase-type distributions and invariant polytopes", Advances in Applied Probability 23(3):515–535, 1991. DOI: 10.2307/1427620, https://doi.org/10.2307/1427620
5. Colm Art O'Cinneide, "Triangular order of triangular phase-type distributions", Communications in Statistics. Stochastic Models 9(4):507–529, 1993. DOI: 10.1080/15326349308807279, https://doi.org/10.1080/15326349308807279
6. Colm Art O'Cinneide, "Phase-type distributions: open problems and a few properties", Communications in Statistics. Stochastic Models 15(4):731–757, 1999. DOI: 10.1080/15326349908807560, https://doi.org/10.1080/15326349908807560
7. A. Cumani, "On the canonical representation of homogeneous Markov processes modelling failure-time distributions", Microelectronics Reliability 22(3):583–602, 1982. DOI: 10.1016/0026-2714(82)90033-6, https://doi.org/10.1016/0026-2714(82)90033-6
8. C. Commault and J. P. Chemla, "An invariant of representations of phase-type distributions and some applications", Journal of Applied Probability 33(2):368–381, 1996. DOI: 10.1017/s0021900200099782, https://doi.org/10.1017/s0021900200099782
9. Commault and Mocanu, "Phase-type distributions and representations: some results and open problems for system theory", International Journal of Control 76(6):566–580, 2003. DOI: 10.1080/0020717031000114986, https://doi.org/10.1080/0020717031000114986
10. David Aldous and Larry Shepp, "The least variable phase type distribution is Erlang", Communications in Statistics. Stochastic Models 3(3):467–473, 1987. DOI: 10.1080/15326348708807067, https://doi.org/10.1080/15326348708807067
11. Qi-Ming He and Hanqin Zhang, "Spectral Polynomial Algorithms for Computing Bi-Diagonal Representations for Phase Type Distributions and Matrix-Exponential Distributions", Stochastic Models 22(2):289–317, 2006. DOI: 10.1080/15326340600649045, https://doi.org/10.1080/15326340600649045
12. Qi-Ming He and Hanqin Zhang, "PH-Invariant Polytopes and Coxian Representations of Phase Type Distributions", Stochastic Models 22(3):383–409, 2006. DOI: 10.1080/15326340600820349, https://doi.org/10.1080/15326340600820349
13. Qi-Ming He and Hanqin Zhang, "On matrix exponential distributions", Advances in Applied Probability 39(1):271–292, 2007. DOI: 10.1239/aap/1175266478, https://doi.org/10.1239/aap/1175266478
14. Qi-Ming He and Hanqin Zhang, "Coxian representations of generalized Erlang distributions", Acta Mathematicae Applicatae Sinica (English Series) 25(3):489–502, 2009. DOI: 10.1007/s10255-008-8827-x, https://doi.org/10.1007/s10255-008-8827-x
15. Mark Fackrell, Qi-Ming He, Peter Taylor, and Hanqin Zhang, "The Algebraic Degree of Phase-Type Distributions", Journal of Applied Probability 47(3):611–629, 2010. DOI: 10.1239/jap/1285335399, https://doi.org/10.1239/jap/1285335399
16. Qi-Ming He, Hanqin Zhang, and Jungong Xue, "Algorithms for Coxianization of Phase-Type Generators", INFORMS Journal on Computing 23(1):153–164, 2011. DOI: 10.1287/ijoc.1100.0383, https://doi.org/10.1287/ijoc.1100.0383
17. Tamás Éltető and Péter Vaderna, "Finding upper-triangular representations for phase-type distributions with 3 distinct real poles", Annals of Operations Research 160(1):139–172, 2008 (first published online 11 December 2007). DOI: 10.1007/s10479-007-0301-2, https://doi.org/10.1007/s10479-007-0301-2
18. Miklós Telek and Gábor Horváth, "A minimal representation of Markov arrival processes and a moments matching method", Performance Evaluation 64(9–12):1153–1168, 2007. DOI: 10.1016/j.peva.2007.06.001, https://doi.org/10.1016/j.peva.2007.06.001
19. Reza Pulungan and Holger Hermanns, "Effective Minimization of Acyclic Phase-Type Representations", in: Analytical and Stochastic Modeling Techniques and Applications (ASMTA/EPEW 2008), Lecture Notes in Computer Science 5055, pp. 128–143, Springer, 2008. DOI: 10.1007/978-3-540-68982-9_10, https://doi.org/10.1007/978-3-540-68982-9_10
20. Reza Pulungan and Holger Hermanns, "Acyclic Minimality by Construction—Almost", Proceedings of the 6th International Conference on the Quantitative Evaluation of Systems (QEST 2009), pp. 63–72, 2009. DOI: 10.1109/QEST.2009.45, https://doi.org/10.1109/QEST.2009.45
21. Eliran Sherzer, Yehezkel Resheff, and Miklós Telek, "An Unconstrained Optimization Approach to Moment Fitting with Phase Type Distributions", preprint, 2025. arXiv:2505.20379, https://arxiv.org/abs/2505.20379
22. András Horváth and Miklós Telek, "Phase Type Distributions", Wiley monograph, 2024. DOI: 10.1002/9781119419808, https://doi.org/10.1002/9781119419808