Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis

Eimutis Valakevičius, Mindaugas Bražėnas and Tomas Ruzgas ()
Additional contact information
Eimutis Valakevičius: Department of Mathematical Modelling, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, Lithuania
Mindaugas Bražėnas: Department of Mathematical Modelling, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, Lithuania
Tomas Ruzgas: Department of Applied Mathematics, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, Lithuania

Mathematics, 2025, vol. 13, issue 2, 1-19

Abstract: We investigate the construction of a partial absorbing continuous-time Markov chain (CTMC) using a heuristic algorithm aimed at approximate transient analysis. The accuracy of transient state probabilities is indicated by the probability of absorbing state(s) at the specified time moment. A key challenge is the construction of a partial CTMC that minimizes the probability of reaching the absorbing state(s). The generation of all possible partial CTMCs is too computationally demanding, in general. Thus, we turn to investigation of heuristic algorithms that chose to include one state at a time based on limited information (i.e., the partial chain that is already constructed) and without any assumptions about the structure of the underlying CTMC. We consider three groups of such algorithms: naive, based on state characterization by the shortest path (obtained by Dijkstra method) and based on exact/approximate state probabilities. After introducing the algorithms, we discuss the problem of optimal partial CTMC construction and provide several examples. Then we compare the algorithm performance by constructing the partial CTMCs for two models: car sharing system and a randomly generated CTMC. Our obtained numerical results suggest that heuristic algorithms using state characterization via the shortest path offer a balance between accuracy and computational effort.

Keywords: continuous-time Markov chain; approximate transient analysis; Dijkstra method; car sharing system (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/2/274/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/2/274/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:2:p:274-:d:1568202

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().