Efficient identification of all equivalent representations of Coxian phase-type distributions: permutation feasibility and complexity

Rizk, Burke and Walsh (2019) proved that any two equivalent representations of an n-phase Coxian phase-type (CPH) distribution have generators with the same diagonal entries up to permutation, and gave an exact algorithm that finds every equivalent representation: enumerate all n! diagonal permutations, solve a nonlinear moment-equality system per permutation, and retain the solutions satisfying Markovian constraints. This constructive enumeration is complete but factorial in cost, and the paper offers no a priori test for which permutations are feasible, no complexity bounds, and no pruning strategy. The open problem is to make this identification tractable: characterize or efficiently decide permutation feasibility without solving the nonlinear system, and obtain provably complete pruning or sub-factorial algorithms.

Background

A phase-type (PH) distribution is the probability law of the time until a finite continuous-time Markov chain reaches an absorbing state. It is specified by a representation $(p,Q)$, where $p$ is a row vector giving the starting probabilities over the $n$ transient states and $Q$ is the $n\times n$ sub-intensity matrix (the transient block of the chain's infinitesimal generator: negative diagonal entries, non-negative off-diagonal entries, and rows summing to strictly negative values, since each transient state has a positive rate of leaving to absorption). PH distributions can approximate any distribution on $[0,\infty)$ arbitrarily well and are standard models for skewed duration data in healthcare, survival analysis, reliability, and queueing.

A Coxian phase-type (CPH) distribution, in the tradition of Cox (1955), is a PH distribution with a strictly sequential latent structure: the chain starts in phase 1, moves from phase $i$ only to phase $i+1$ at rate $\lambda_i$, and is absorbed from phase $i$ at rate $\mu_i$. Its generator is upper bidiagonal, and a non-redundant order-$n$ representation ($n$-CPH) carries exactly $2n-1$ parameters - the same as the number of non-trivial coefficients of the distribution's Laplace transform - so no parameter can be dropped without shrinking the representable class. The expected length of stay in phase $k$ is $LoS_k=1/(\lambda_k+\mu_k)$, the negative reciprocal of the $k$-th diagonal entry of $Q$; in applications such as hospital length-of-stay modelling these latent phase durations carry the scientific interpretation of the fitted model.

The representation is nevertheless not unique. Maximum-likelihood fits of an $n$-CPH model started from different initial values can converge to different parameter vectors with exactly equal likelihood, because distinct parameter sets can induce the same distribution (equivalent representations), making the likelihood surface multi-modal. Each mode corresponds to a different ordering of the phase durations, i.e. a different data-generating narrative, so a modeller choosing one representation on substantive grounds first needs all of them - and repeated refitting gives no guarantee of finding them all.

Classical theory characterizes equivalence only between two given representations, not how to enumerate them. O'Cinneide (1989) introduced the phase-type simplicity and majorization concepts, and Telek and Horváth (2007) gave a transformation-matrix characterization together with a minimal-representation method; both verify candidate pairs rather than generating all representations. Cumani (1982) showed every acyclic (upper-triangular) PH distribution has a canonical bidiagonal Coxian form - which, as later literature recounts, is always valid when the eigenvalues are sorted on the diagonal - and Mocanu and Commault (1999) studied sparse representations and monocyclic ones (generators formed from a single directed cycle of Erlang chains, each chain a run of phases with a single exit). In the generalized Erlang (hypoexponential) subcase the superdiagonal equals minus the diagonal, so permuting the diagonal entries trivially produces all equivalent representations (Reinecke et al., 2010); the case of feedback-Erlang blocks (Erlang chains closed by a single feedback loop) behaves similarly (Horváth et al., 2016). He and Zhang (2006, 2006, 2008) developed spectral polynomial algorithms that compute ordered Coxian (bidiagonal) representations in polynomial time, PH-invariant polytopes, and an algorithm for minimal Coxian representations - work that fixes a canonical eigenvalue ordering and targets order reduction, not the question of which orderings are simultaneously realizable.

Rizk, Burke and Walsh (2019) closed the enumeration gap for the Coxian class. They proved that two equivalent non-redundant PH representations are related by a nonsingular transformation matrix $M$ with $p_b=p_aM$, $Q_b=M^{-1}Q_aM$ and $Mq_b=q_a$; that for CPH distributions $M$ is lower triangular with first row $(1,0,\ldots,0)$; that the first absorbing rate $\mu_1$ is invariant across equivalent representations; and that equivalent CPH generators have the same diagonal entries up to permutation. Their algorithm therefore runs over all permutations $V^{(r)}$ of $\mathrm{diag}(Q_a)$ (up to $n!$ of them): for each permutation, $b_{12}$ follows directly from the invariance of $\mu_1$, and the remaining $n-2$ superdiagonal entries of the candidate generator $Q_b$ are obtained as the unique solution of the moment-equality system

$$p_a(-Q_a)^{-k}\mathbf{1}=p_b(-Q_b)^{-k}\mathbf{1}, \qquad k=1,\ldots,n-2,$$

where $\mathbf{1}$ is the all-ones vector. The permutation is feasible precisely when this unique solution satisfies the Markovian constraints $0<b_{i,i+1}\le -V^{(r)}_i$ for $i=1,\ldots,n-1$, and the feasible permutations are exactly the equivalent representations. The construction is exact and complete, but it costs a factorial enumeration with one nonlinear solve per permutation; the authors note that the runs can be parallelized and that applications rarely need $n\ge 10$ phases.

Problem Statement

Let $(p_a,Q_a)$ with $p_a=(1,0,\ldots,0)$ be a non-redundant order-$n$ Coxian phase-type representation with upper-bidiagonal generator, and let $V^{(r)}$ range over the permutations of $\mathrm{diag}(Q_a)$ (up to $n!$ of them). For each permutation, the Rizk-Burke-Walsh construction yields a unique candidate equivalent generator $Q_b$ with diagonal $V^{(r)}$: $b_{12}$ is fixed by the invariance of the first absorbing rate $\mu_1$, and the remaining $n-2$ superdiagonal entries are the unique solution of the moment-equality system $p_a(-Q_a)^{-k}\mathbf{1}=p_b(-Q_b)^{-k}\mathbf{1}$, $k=1,\ldots,n-2$. The permutation is feasible iff this solution satisfies $0<b_{i,i+1}\le -V^{(r)}_i$ for all $i$, and the feasible permutations are exactly the equivalent representations of the given distribution.

The open problem is the tractability of this constructive enumeration, as left unresolved by the source:

1. Permutation feasibility and complexity (core). The first target is an exact feasibility decision: decide, without solving the nonlinear moment system, which permutations of the diagonal are feasible. A polynomial-time feasibility procedure (in $n$ and the bit-length of the generator entries) resolves this target, and a structural characterization that makes feasibility decidable counts as a resolution as well. The second target is the complexity of complete enumeration: a provably complete algorithm that returns all feasible permutations using $o(n!)$ worst-case verification work per instance, with output time proportional to the number of feasible permutations allowed (that number can be as large as $n!$, for example when every diagonal permutation is feasible). Count distinct permutations when diagonal entries repeat.
2. Pruning with a completeness guarantee. Any rule that discards permutations before solving must provably never discard a feasible one, preserving the source's guarantee that all representations are found; heuristic pruning without such a guarantee does not resolve this component. The rule must also cut the worst-case solve count: as the order $n$ grows, over all admissible order-$n$ inputs it must reduce the number of nonlinear solves below the exhaustive $n!$ by a non-constant factor (equivalently, achieve $o(n!)$ worst-case solves), with output kept separate from the solve count. A sound but solve-free rule that still performs $n!$ solves in the worst case - for instance, one that discards nothing on some admissible input - does not meet this standard.

Items 1 and 2 form the objective: an exact feasibility decision and the complexity of complete enumeration for the constructive identification of all equivalent representations. Partial results (for example a criterion for small $n$, for distinct and well-separated eigenvalues, or for hypoexponential limits) are genuine progress but do not by themselves resolve the problem; the target is the general non-redundant Coxian case.

References

1. Rizk, J., Burke, K., Walsh, C. (2019). On the Non-uniqueness of Representations of Coxian Phase-Type Distributions. arXiv:1901.03849 (v2). DOI: 10.48550/arXiv.1901.03849. https://arxiv.org/abs/1901.03849
2. Lindqvist, B. H. (2023). Phase-type models for competing risks, with emphasis on identifiability issues. Lifetime Data Analysis 29(2), 318-341. DOI: 10.1007/s10985-022-09547-7. https://doi.org/10.1007/s10985-022-09547-7
3. Rizk, J., Walsh, C., Burke, K. (2021). An alternative formulation of Coxian phase-type distributions with covariates: Application to emergency department length of stay. Statistics in Medicine 40(6), 1574-1592. DOI: 10.1002/sim.8860. https://doi.org/10.1002/sim.8860
4. Cox, D. R. (1955). A use of complex probabilities in the theory of stochastic processes. Mathematical Proceedings of the Cambridge Philosophical Society 51(2), 313-319. DOI: 10.1017/s0305004100030231. https://doi.org/10.1017/s0305004100030231
5. Cumani, A. (1982). On the canonical representation of homogeneous Markov processes modelling failure-time distributions. Microelectronics Reliability 22(3), 583-602. DOI: 10.1016/0026-2714(82)90033-6. https://doi.org/10.1016/0026-2714(82)90033-6
6. O'Cinneide, C. A. (1989). On non-uniqueness of representations of phase-type distributions. Communications in Statistics. Stochastic Models 5(2), 247-259. DOI: 10.1080/15326348908807108. https://doi.org/10.1080/15326348908807108
7. Telek, M., Horváth, G. (2007). A minimal representation of Markov arrival processes and a moments matching method. Performance Evaluation 64(9-12), 1153-1168. DOI: 10.1016/j.peva.2007.06.001. https://doi.org/10.1016/j.peva.2007.06.001
8. Mocanu, S., Commault, C. (1999). Sparse representations of phase-type distributions. Communications in Statistics. Stochastic Models 15(4), 759-778. DOI: 10.1080/15326349908807561. https://doi.org/10.1080/15326349908807561
9. Reinecke, P., Telek, M., Wolter, K. (2010). Reducing the Cost of Generating APH-Distributed Random Numbers. Lecture Notes in Computer Science, 274-286. DOI: 10.1007/978-3-642-12104-3_21. https://doi.org/10.1007/978-3-642-12104-3_21
10. 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
11. He, Q.-M., Zhang, H. (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
12. He, Q.-M., Zhang, H. (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
13. He, Q.-M., Zhang, H. (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
14. 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. arXiv:2409.12673. DOI: 10.1017/apr.2024.72. https://arxiv.org/abs/2409.12673
15. Albrecher, H., Gardner, C. B., Nielsen, B. F. (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
16. Sherzer, E., Resheff, Y., Telek, M. (2025). An Unconstrained Optimization Approach to Moment Fitting with Phase Type Distributions. arXiv:2505.20379. DOI: 10.48550/arXiv.2505.20379. https://arxiv.org/abs/2505.20379
17. Rostami, A., Hassan Zadeh, A. (2024). A Markovian Aging Process Forecasting Model: Predicting U.S. Mortality. North American Actuarial Journal 29(1), 224-245. DOI: 10.1080/10920277.2024.2325343. https://doi.org/10.1080/10920277.2024.2325343
18. Hurtado, P. J., Richards, C. (2021). Building mean field ODE models using the generalized linear chain trick & Markov chain theory. Journal of Biological Dynamics 15(sup1), S248-S272. DOI: 10.1080/17513758.2021.1912418. https://doi.org/10.1080/17513758.2021.1912418
19. Peralta, O. (2026). Equivalence and Separation for Multivariate Matrix-Exponential and Phase-Type Distribution Classes. arXiv:2605.15395. DOI: 10.48550/arXiv.2605.15395. https://arxiv.org/abs/2605.15395