A phase-type (PH) distribution is represented by an initial probability vector and a transient generator matrix, but this representation is non-unique and over-parameterized, and a canonical — unique, minimal, and symbolically computable — representation is known only for acyclic PH(n), for PH(2), and, by Horváth and Telek (2009), for the general order-3 class PH(3). For order four the natural unicyclic parametrization (the generator parameters x1,x2,x3,x4,x13,x14x_1,x_2,x_3,x_4,x_{13},x_{14} of equations (27)–(30) of Horváth and Telek 2009) leads to a degree-6 algebraic equation, and the authors conjecture that PH(3) is the highest order for which a symbolic canonical transformation exists. This problem asks whether that conjecture holds: either construct a canonical representation of the general PH(4) class — a unique minimal 7-parameter Markovian form together with a closed-form transformation from any order-4 representation — or prove that no symbolic canonical form exists for PH(4), and for the full conjecture for PH(n) with n ≥ 4. The problem remains open.

Background

A phase-type (PH) distribution of order nn is the time to absorption of a finite continuous-time Markov chain with nn transient states and one absorbing state. Its transient structure is encoded by an initial probability row vector vv and a sub-generator matrix HH (the transient block of the chain's generator: negative diagonal, non-negative off-diagonal entries, non-positive row sums), giving density f(t)=veHt(−H)1f(t)=v e^{Ht}(-H)\mathbf{1}, where 1\mathbf{1} is the all-ones column vector. PH distributions are dense in the non-negative distributions and are the standard vehicle for embedding empirically observed times into Markovian queueing, reliability, and risk models. Their representational weakness is the starting point of this problem: the pair (v,H)(v,H) is neither unique nor parsimonious — it carries n2+n−1n^2+n-1 free parameters while the distribution is fixed by only 2n−12n-1 scalars, the coefficients of its Laplace transform, a rational function whose denominator degree (the algebraic degree of the distribution) is at most nn. A canonical representation is a unique minimal description of the distribution inside its class, with exactly 2n−12n-1 parameters, together with a transformation producing it from any given representation of the same distribution; it plays the role of a normal form and underlies identifiability, uniqueness in parameter fitting, exact feasibility testing, and analytic moment-region computations.

For acyclic PH distributions (no directed cycle among transient states) a canonical form has been known since Cumani (1982), and because every PH(2) distribution is similar to an acyclic one (Cox, 1955), the general order-2 class is covered as well. The first genuinely cyclic order is n=3n=3: He and Zhang (2005) proved that every PH(3) distribution admits a unicyclic representation, meaning a generator whose transient-state graph contains a single directed cycle. Building on this, Horváth and Telek (2007; 2009) constructed the canonical representation of the general PH(3) class: a unicyclic Markovian pair (π,A)(\pi,A) with exactly 2⋅3−1=52\cdot3-1=5 parameters, existing for every PH(3) distribution and unique in the strong sense that any two representations of the same distribution transform to the same canonical pair. The transformation is symbolic: the canonical parameters are written in closed form in terms of the representation invariants — the eigenvalues λi\lambda_i of −H-H and the derivatives di=−vHi1d_i=-v H^i\mathbf{1} — with the only root-taking being that of a cubic polynomial, for which a formula in radicals exists. The construction doubles as a feasibility test (an order-3 vector–matrix pair is PH(3) exactly when the transformation succeeds) and enabled the first, numerical, exploration of the feasible region of normalized moments n2=μ2/μ12n_2=\mu_2/\mu_1^2, n3=μ3/(μ1μ2)n_3=\mu_3/(\mu_1\mu_2), and higher, of the PH(3) class.

For order four the same program stalls. The natural unicyclic PH(4) parametrization has six generator parameters x1,x2,x3,x4,x13,x14x_1,x_2,x_3,x_4,x_{13},x_{14} related to the characteristic coefficients a0,…,a3a_0,\dots,a_3 of −H-H by four polynomial equations (equations (27)–(30) of Horváth and Telek 2009); with x1x_1 and x13x_{13} fixed, the remaining parameters satisfy a single algebraic equation of degree six (their Corollary 1). Since polynomial equations of degree five and higher are in general not solvable in radicals, the authors conclude that no symbolic canonical transformation analogous to the PH(3) construction can be derived for PH(4) within this parametrization once x1x_1 and x13x_{13} are fixed, in contrast to the order-3 case where the cubic formula suffices. The full (π,A)(\pi,A) PH(4) family has nine parameters — the six generator entries x1,x2,x3,x4,x13,x14x_1,x_2,x_3,x_4,x_{13},x_{14} together with the three initial-vector components π1,π2,π3\pi_1,\pi_2,\pi_3 — two more than the minimal number 2⋅4−1=72\cdot4-1=7, and the paper lists candidate constraint pairs (setting one of x13,x14,π2,π3x_{13},x_{14},\pi_2,\pi_3 to zero, or equating consecutive rates x1=x2x_1=x_2, x2=x3x_2=x_3, x3=x4x_3=x_4) without identifying a canonical choice; both the coverage of the whole PH(4) class by this family and any canonical selection are supported only by numerical experiments. The paper concludes that the canonical representation of higher-order PH classes is still open and conjectures that PH(3) is the highest order for which a symbolic canonical transformation exists. The question is also recognized as an open problem in the system-theory literature on positive realizations (O'Cinneide 1999; Commault and Mocanu 2003), since a PH representation is precisely a positive realization of a rational transfer function.

Problem Statement

Decide whether the general phase-type class of order four — and, in its full form, PH(nn) for every n≥4n\ge4 — admits a canonical representation in the sense established for order three: an assignment to each distribution of the class of a unique Markovian representation with exactly 2n−12n-1 parameters, together with a symbolic (closed-form) transformation that computes it from an arbitrary order-nn vector–matrix representation of the same distribution, with parameters expressed in the representation invariants (the eigenvalues of −H-H and the derivatives di=−vHi1d_i=-v H^i\mathbf{1}).

For the decisive case n=4n=4 the question asks whether such a canonical representation exists:

  1. Construction. Exhibit a canonical family for PH(4) — a minimal 7-parameter Markovian family — and prove: (i) coverage, that every PH(4) distribution, including degenerate members such as coincident eigenvalues, acyclic limits, and zero density at the origin, admits a representation in the family; (ii) minimality, that the family has exactly seven independent parameters, as a family-level dimension claim, with degenerate lower-order members arising as boundary specializations rather than being excluded; (iii) uniqueness, that any two representations of the same distribution transform to the same canonical pair; and (iv) symbolicity, that the transformation's parameters are given in closed form in the invariants in the sense of the formalization described in branch 2 (a finite closed-form expression, for example in radicals, over the field generated by the invariant coefficients of the Laplace transform). A construction covering only a proper subclass of PH(4), or verified only numerically over samples, does not answer the question.

  2. Impossibility. Formalize the notion of a symbolic canonical transformation (a finite closed-form expression, for example in radicals, over the field generated by the invariant coefficients of the Laplace transform) and prove that no such transformation to a unique minimal Markovian representation exists for PH(4); extending the argument to every n≥4n\ge4 settles the source's conjecture that PH(3) is the highest order admitting a symbolic canonical transformation. An impossibility argument that relies only on the degree-6 elimination inside the single unicyclic parametrization of Corollary 1 is insufficient, since the obstruction must be shown for all admissible parametrizations; under any proposed formalization, the admissible class may not be narrowed so as to exclude parametrizations capable of carrying a canonical representation and thereby make the obstruction trivial.

References

  1. Gábor Horváth and Miklós Telek, On the canonical representation of phase type distributions, Performance Evaluation 66(8):396–409, 2009. DOI: 10.1016/j.peva.2008.11.002, https://doi.org/10.1016/j.peva.2008.11.002 (full text: https://webspn.hit.bme.hu/~telek/cikkek/horv08b.pdf)
  2. Gábor Horváth and Miklós Telek, A Canonical Representation of Order 3 Phase Type Distributions, in Formal Methods and Stochastic Models for Performance Evaluation (EPEW 2007), Lecture Notes in Computer Science, pp. 48–62, 2007. DOI: 10.1007/978-3-540-75211-0_5, https://doi.org/10.1007/978-3-540-75211-0_5
  3. Qi-Ming He and Hanqin Zhang, A Note on Unicyclic Representations of Phase Type Distributions, Stochastic Models 21:465–483, 2005. DOI: 10.1081/stm-200057131, https://doi.org/10.1081/stm-200057131
  4. A. Cumani, On the canonical representation of homogeneous Markov processes modelling failure-time distributions, Microelectronics and Reliability 22:583–602, 1982. DOI: 10.1016/0026-2714(82)90033-6, https://doi.org/10.1016/0026-2714(82)90033-6
  5. D. R. Cox, A use of complex probabilities in the theory of stochastic processes, Mathematical Proceedings of the Cambridge Philosophical Society 51:313–319, 1955. DOI: 10.1017/s0305004100030231, https://doi.org/10.1017/s0305004100030231
  6. C. A. O'Cinneide, Phase-type distributions: open problems and a few properties, Stochastic Models 15(3):731–757, 1999. DOI: 10.1080/15326349908807560, https://doi.org/10.1080/15326349908807560
  7. C. Commault and S. 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
  8. Illés Horváth, János Papp, and Miklós Telek, On the Canonical Representation of Order 3 Discrete Phase Type Distributions, Electronic Notes in Theoretical Computer Science 318:143–158, 2015. DOI: 10.1016/j.entcs.2015.10.024, https://doi.org/10.1016/j.entcs.2015.10.024
  9. 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)
  10. András Horváth, Sándor Rácz, and Miklós Telek, Moments Characterization of Order 3 Matrix Exponential Distributions, in Analytical and Stochastic Modeling Techniques and Applications (ASMTA 2009), Lecture Notes in Computer Science, pp. 174–188, 2009. DOI: 10.1007/978-3-642-02205-0_13, https://doi.org/10.1007/978-3-642-02205-0_13
  11. Qi-Ming He, Gábor Horváth, Illés Horváth, and Miklós Telek, Moment bounds of PH distributions with infinite or finite support based on the steepest increase property, Advances in Applied Probability 51(1):168–183, 2019. DOI: 10.1017/apr.2019.7, https://doi.org/10.1017/apr.2019.7
  12. Gábor Horváth and Miklós Telek, Markovian Performance Evaluation with BuTools, in Systems Modeling: Methodologies and Tools, Springer, pp. 253–268, 2019. DOI: 10.1007/978-3-319-92378-9_16, https://doi.org/10.1007/978-3-319-92378-9_16
  13. 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
  14. A. Bobbio, A. Horváth, and M. Telek, Matching three moments with minimal acyclic phase-type distributions, Stochastic Models 21(2–3):303–326, 2005. DOI: 10.1081/stm-200056210, https://doi.org/10.1081/stm-200056210