Graph-based algorithms for phase-type distributions

Tobias Røikjer, Asger Hobolth, Kasper Munch*

*Corresponding author for this work

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Abstract

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.

Original languageEnglish
Article number103
JournalStatistics and Computing
Volume32
Issue6
ISSN0960-3174
DOIs
Publication statusPublished - Dec 2022

Keywords

  • Computational statistics
  • Distribution
  • Graph-based algorithms
  • Moments
  • Phase-type distributions

Fingerprint

Dive into the research topics of 'Graph-based algorithms for phase-type distributions'. Together they form a unique fingerprint.

Cite this