Minimal-order phase-type representations beyond three distinct real poles: extending the invariant-polytope construction to more, repeated, and complex poles, with global guarantees

Éltető and Vaderna (2008) solved the minimal-representation problem constructively for one family of matrix-exponential distributions: those whose Laplace–Stieltjes transform has exactly three distinct real poles. Working in a canonical two-dimensional affine plane, they characterized the minimal order among upper-triangular (Coxian) phase-type representations through invariant polytopes $S_n$ with recursively defined borders $L_n$, and gave a generator-recovery procedure producing a Markovian representation of provably minimal upper-triangular order. Beyond that construction, the following remain open: it does not cover four or more distinct real poles, repeated real poles, or complex conjugate poles; the nonsingularity of the auxiliary linear systems in the $L_n$ recursion is required but not guaranteed globally; criteria for selecting the feasible solution among multiple algebraic solutions are not formalized; and the redundant eigenvalues forced into minimal representations whose order exceeds the algebraic degree (the number of poles counted with multiplicity) are unanalyzed. This problem asks for the extension of that constructive minimal-order theory to the remaining pole regimes together with the missing global guarantees.

Background

A phase-type (PH) distribution is the law of the time to absorption in a finite continuous-time Markov chain (CTMC) with a single absorbing state: with initial probability row vector $\alpha$ over the transient states and subgenerator $\mathbf{S}$ (a matrix with nonnegative off-diagonal entries and nonpositive row sums), the density is $f(t)=\alpha e^{\mathbf{S}t}\mathbf{s}$ with exit-rate vector $\mathbf{s}=-\mathbf{S}\mathbf{1}$. PH distributions are dense among distributions on the positive half-line and underpin matrix-analytic methods in queueing, reliability, risk, and biology; the number of phases (the order, i.e. the dimension of $\mathbf{S}$) drives both computational cost and statistical stability, so small representations matter. A matrix-exponential (ME) distribution is a density of the same functional form $\alpha e^{\mathbf{S}t}\mathbf{s}$ where $\alpha$ and $\mathbf{S}$ are merely real (no Markovian interpretation required); O'Cinneide's characterization theorem states that such a density is a PH density exactly when it is strictly positive on $(0,\infty)$ and its transform satisfies a dominant-eigenvalue condition, and Horváth and Telek (2015) gave a constructive proof. The Laplace–Stieltjes transform (LST) of such a density is rational; its poles are the eigenvalues of $\mathbf{S}$. The order of a representation and the algebraic degree of the distribution — the degree of the LST denominator, equivalently the number of poles counted with multiplicity (Fackrell, He, Taylor and Zhang, 2010) — need not agree: the degree is a lower bound on every PH order, and Commault and Chemla (1996) proved that when the LST numerator has degree at most one and all poles are real, the order equals the degree, while showing that with complex poles, or with a numerator of degree two or more, the minimal order can be dramatically larger than the degree. Finding the minimal PH order of a given distribution is a recognized open problem (O'Cinneide, 1999; Commault and Mocanu, 2003).

Among structured representations, the cheapest are the acyclic ones, and in particular the bi-diagonal (upper-triangular, Coxian) representations in which $\mathbf{S}$ is upper bidiagonal; a real upper-triangular matrix has its eigenvalues on the diagonal, hence real, so such representations exist only for real-pole distributions. O'Cinneide (1991) developed the geometric theory of invariant polytopes — convex sets of probability vectors closed under the flow induced by $\mathbf{S}$, a picture initiated by Dehon and Latouche (1982) for small orders — using it to derive lower bounds on the order from the poles and to prove that every PH distribution whose transform has only real poles admits a bi-diagonal representation. He and Zhang (2006) developed PH-invariant polytopes into generic algorithms for bi-diagonal representations, alongside spectral-polynomial algorithms computing bi-diagonal representations directly from spectrum data (He and Zhang, 2006), and an algorithm for minimal ordered Coxian representations of PH distributions with only real poles (He and Zhang, 2008).

Éltető and Vaderna (2008) treated the matrix-exponential family with exactly three distinct real poles. Fixing the poles, the densities of the family are parametrized in a canonical real two-dimensional affine plane with coordinates $(\eta_1,\eta_2)$. They construct sets $S_n$ in this plane — $S_1$ consists of three points, $S_2$ of three segments (the Dehon–Latouche picture), and $S_3$ contains a quadrangular part $C_4^*$ bounded by a line $L_3$ — such that membership in $S_n$ characterizes the minimal order $n$ among upper-triangular representations, with the borders $L_n$ for $n\ge4$ defined recursively through tangency and parallelism conditions on a planar vector field, which requires solving auxiliary linear systems for tangential coefficients $c_1,\dots,c_{n-5}$; a generator of the minimal representation is then recovered via the relation $\mathbf{M}=\mathbf{G}\mathbf{S}^{\#}+\mathbf{K}$ with $\mathbf{K}\mathbf{S}=0$, where $\mathbf{S}^{\#}$ is the group inverse (the standard generalized inverse of $\mathbf{S}$). A worked example at order six exhibits redundant, nearly equal eigenvalues produced by finite precision — a structural nuisance, since any representation whose order exceeds the algebraic degree must carry redundant eigenvalues, i.e. eigenvalues that are not poles of the transform.

The construction covers only the three-distinct-real-pole case: more poles, repeated poles, and complex conjugate poles require different machinery (for complex poles, upper-triangular representations are impossible and the question necessarily concerns cyclic Markovian representations, i.e. generators containing a directed cycle, the simplest being unicyclic representations whose transition graph contains exactly one cycle); the Non-singularity Condition on the auxiliary linear systems required by the recursion is checked case by case, not guaranteed globally; the nonlinear $L_n$ equations can have several algebraic solutions, some infeasible, without formalized selection criteria; and, since the paper's minimality result is confined to the upper-triangular class, the relation between minimal upper-triangular order and minimal order among all PH representations is left open. The current state of the art confirms the gap: the He–Zhang program covers per-instance computation in the real-pole regime (spectral polynomials 2006; invariant polytopes 2006; minimal Coxian algorithm 2008; generalized Erlang, i.e. one repeated-pole subclass, 2009; Coxianization, i.e. transformation into Coxian form, of generators with real eigenvalues, with Xue, 2011), while He and Zhang (2005) showed by counterexample that not every PH representation has an equivalent unicyclic representation of the same order, though the conjecture does hold at order three; Liu, Yao and Zhang (2024, 2025) recast representation search as a non-convex optimization problem and give an if-and-only-if test for the existence of a representation whose order equals the algebraic degree, stating plainly that the minimal PH representation problem remains far from solved and naming, as the next research topic, exactly the case where the order must exceed the degree — identifying which additional poles a minimal representation is forced to carry.

Problem Statement

Extend the constructive minimal-order representation theory of Éltető and Vaderna (2008) beyond matrix-exponential families with exactly three distinct real poles, and supply its missing global guarantees. For a matrix-exponential family whose Laplace–Stieltjes transform has a given pole structure, with minimal order understood within the class of representations specified in each part:

(1) Real poles, any number or repetition. For families with four or more distinct real poles, and for families with repeated real poles, give the analogue of the invariant-polytope construction: a parametrization of the family in suitable canonical coordinates; a classification of the parameter space into regions $S_n$ characterizing the minimal upper-triangular (Coxian) order $n$; explicit recursive equations for the region borders generalizing the $L_n$ tangency/parallelism systems and their tangential coefficients $c_1,\dots,c_{n-5}$; and a generator-recovery procedure producing a representation of provably minimal upper-triangular order.

(2) Complex conjugate poles. Since real upper-triangular matrices have real eigenvalues, such families admit no upper-triangular representation; extend the invariant-polytope method to them via an appropriate coordinate reduction and characterize the minimal order among Markovian (necessarily cyclic, e.g. unicyclic) representations, constructively recovering a representation attaining it.

(3) Global guarantees. Establish, or refute by explicit counterexample, the Non-singularity Condition: that the auxiliary linear systems of the generalized $L_n$ recursion are nonsingular for all relevant argument tuples, with a characterization of the degenerate configurations; formalize verifiable criteria that select, among the multiple algebraic solutions of the nonlinear $L_n$-type equations, those yielding valid absolutely continuous densities; and characterize the redundant eigenvalues (eigenvalues of the representation that are not poles of the transform) forced into a minimal representation whose order exceeds the algebraic degree.

(4) Triangular versus general order. Determine, at least for the families in (1), how the minimal upper-triangular order relates to the minimal order among all phase-type representations.

Parts (1)–(4) are posed independently of one another: (1) and (2) address the further real- and complex-pole regimes, (3) the global guarantees, and (4) the relation between minimal upper-triangular order and minimal order among all phase-type representations.

These parts share one objective: a representation theory in which the minimal structured order and an attaining representation are read off constructively from the pole data of the transform, replacing per-instance numerical search.

References

1. Éltető, Tamás; Vaderna, Péter (2008), 'Finding upper-triangular representations for phase-type distributions with 3 distinct real poles', Annals of Operations Research 160(1):139–172, DOI 10.1007/s10479-007-0301-2, https://doi.org/10.1007/s10479-007-0301-2
2. O'Cinneide, Colm Art (1991), 'Phase-type distributions and invariant polytopes', Advances in Applied Probability 23(3):515–535, DOI 10.2307/1427620, https://doi.org/10.2307/1427620
3. Dehon, Michel; Latouche, Guy (1982), 'A geometric interpretation of the relations between the exponential and generalized Erlang distributions', Advances in Applied Probability 14(4):885–897, DOI 10.2307/1427029, https://doi.org/10.2307/1427029
4. O'Cinneide, Colm Art (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
5. Commault, C.; Chemla, J. P. (1996), 'An invariant of representations of phase-type distributions and some applications', Journal of Applied Probability 33(2):368–381, DOI 10.1017/s0021900200099782, https://doi.org/10.1017/s0021900200099782
6. Commault, Christian; Mocanu, Stéphane (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
7. He, Qi-Ming; Zhang, Hanqin (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
8. He, Qi-Ming; Zhang, Hanqin (2006), 'Spectral polynomial algorithms for computing bi-diagonal representations for phase type distributions and matrix-exponential distributions', Stochastic Models 22(2):289–317, DOI 10.1080/15326340600649045, https://doi.org/10.1080/15326340600649045
9. He, Qi-Ming; Zhang, Hanqin (2006), 'PH-invariant polytopes and Coxian representations of phase type distributions', Stochastic Models 22(3):383–409, DOI 10.1080/15326340600820349, https://doi.org/10.1080/15326340600820349
10. He, Qi-Ming; Zhang, Hanqin (2007), 'On matrix exponential distributions', Advances in Applied Probability 39(1):271–292, DOI 10.1239/aap/1175266478, https://doi.org/10.1239/aap/1175266478
11. He, Qi-Ming; Zhang, Hanqin (2008), 'An algorithm for computing minimal Coxian representations', INFORMS Journal on Computing 20(2):179–190, DOI 10.1287/ijoc.1070.0228, https://doi.org/10.1287/ijoc.1070.0228
12. He, Qi-ming; Zhang, Han-qin (2009), 'Coxian representations of generalized Erlang distributions', Acta Mathematicae Applicatae Sinica (English Series) 25(3):489–502, DOI 10.1007/s10255-008-8827-x, https://doi.org/10.1007/s10255-008-8827-x
13. He, Qi-Ming; Zhang, Hanqin; Xue, Jungong (2011), 'Algorithms for Coxianization of phase-type generators', INFORMS Journal on Computing 23(1):153–164, DOI 10.1287/ijoc.1100.0383, https://doi.org/10.1287/ijoc.1100.0383
14. Fackrell, Mark; He, Qi-Ming; Taylor, Peter; Zhang, Hanqin (2010), 'The algebraic degree of phase-type distributions', Journal of Applied Probability 47(3):611–629, DOI 10.1239/jap/1285335399, https://doi.org/10.1239/jap/1285335399
15. Horváth, Illés; Telek, Miklós (2015), 'A constructive proof of the phase-type characterization theorem', arXiv:1502.00521, https://arxiv.org/abs/1502.00521
16. Horváth, Gábor; Telek, Miklós (2017), 'BuTools 2: a rich toolbox for Markovian performance evaluation', Proceedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools, DOI 10.4108/eai.25-10-2016.2266400, https://doi.org/10.4108/eai.25-10-2016.2266400
17. Varmazyar, Mohsen; Akhavan-Tabatabaei, Raha; Salmasi, Nasser; Modarres, Mohammad (2019), 'Classification and properties of acyclic discrete phase-type distributions based on geometric and shifted geometric distributions', Journal of Industrial Engineering International 15(4):651–665, DOI 10.1007/s40092-018-0299-x, https://doi.org/10.1007/s40092-018-0299-x (online first November 2018)
18. Rizk, Jean; Burke, Kevin; Walsh, Cathal (2019), 'On the non-uniqueness of representations of Coxian phase-type distributions', arXiv:1901.03849, https://arxiv.org/abs/1901.03849
19. Liu, Yujie; Yao, Dacheng; Zhang, Hanqin (2024), 'On substochastic inverse eigenvalue problems with the corresponding eigenvector constraints', SIAM Journal on Matrix Analysis and Applications 45(3):1689–1719, DOI 10.1137/23m1547305, https://doi.org/10.1137/23m1547305
20. Liu, Yujie; Yao, Dacheng; Zhang, Hanqin (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, arXiv:2409.12673, https://arxiv.org/abs/2409.12673
21. Albrecher, Hansjörg; Brimnes Gardner, Clara; Nielsen, Bo Friis (2025), 'Phase-type representations for exponential distributions', Advances in Applied Probability 57(3):969–999, DOI 10.1017/apr.2024.67, https://doi.org/10.1017/apr.2024.67