Details

Autor(en) / Beteiligte

• Røikjer, Tobias
• Hobolth, Asger
• Munch, Kasper

Titel

Graph-based algorithms for phase-type distributions

Ist Teil von

• Statistics and computing, 2022-12, Vol.32 (6), Article 103

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2022

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Phase-type distributions model the time until absorption in continuous or discrete-time Markov chains on a finite state space. The multivariate phase-type distributions have diverse and important applications by modeling rewards accumulated at visited states. However, even moderately sized state spaces make the traditional matrix-based equations computationally infeasible. State spaces of phase-type distributions are often large but sparse, with only a few transitions from a state. This sparseness makes a graph-based representation of the phase-type distribution more natural and efficient than the traditional matrix-based representation. In this paper, we develop graph-based algorithms for analyzing phase-type distributions. In addition to algorithms for state space construction, reward transformation, and moments calculation, we give algorithms for the marginal distribution functions of multivariate phase-type distributions and for the state probability vector of the underlying Markov chains of both time-homogeneous and time-inhomogeneous phase-type distributions. The algorithms are available as a numerically stable and memory-efficient open source software package written in C named ptdalgorithms. This library exposes all methods in the programming languages C and R. We compare the running time of ptdalgorithms to the fastest tools using a traditional matrix-based formulation. This comparison includes the computation of the probability distribution, which is usually computed by exponentiation of the sub-intensity or sub-transition matrix. We also compare time spent calculating the moments of (multivariate) phase-type distributions usually defined by inversion of the same matrices. The numerical results of our graph-based and traditional matrix-based methods are identical, and our graph-based algorithms are often orders of magnitudes faster. Finally, we demonstrate with a classic problem from population genetics how ptdalgorithms serves as a much faster, simpler, and completely general modeling alternative.