Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis
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 chal...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/2/274 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832588074725408768 |
|---|---|
| author | Eimutis Valakevičius Mindaugas Bražėnas Tomas Ruzgas |
| author_facet | Eimutis Valakevičius Mindaugas Bražėnas Tomas Ruzgas |
| author_sort | Eimutis Valakevičius |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-93bd9aacad6243cd9798296fe6322599 |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-93bd9aacad6243cd9798296fe63225992025-01-24T13:40:00ZengMDPI AGMathematics2227-73902025-01-0113227410.3390/math13020274Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient AnalysisEimutis Valakevičius0Mindaugas Bražėnas1Tomas Ruzgas2Department of Mathematical Modelling, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, LithuaniaDepartment of Mathematical Modelling, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, LithuaniaDepartment of Applied Mathematics, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, LithuaniaWe 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.https://www.mdpi.com/2227-7390/13/2/274continuous-time Markov chainapproximate transient analysisDijkstra methodcar sharing system |
| spellingShingle | Eimutis Valakevičius Mindaugas Bražėnas Tomas Ruzgas Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis Mathematics continuous-time Markov chain approximate transient analysis Dijkstra method car sharing system |
| title | Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis |
| title_full | Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis |
| title_fullStr | Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis |
| title_full_unstemmed | Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis |
| title_short | Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis |
| title_sort | comparison of continuous time partial markov chain construction by heuristic algorithms for purpose of approximate transient analysis |
| topic | continuous-time Markov chain approximate transient analysis Dijkstra method car sharing system |
| url | https://www.mdpi.com/2227-7390/13/2/274 |
| work_keys_str_mv | AT eimutisvalakevicius comparisonofcontinuoustimepartialmarkovchainconstructionbyheuristicalgorithmsforpurposeofapproximatetransientanalysis AT mindaugasbrazenas comparisonofcontinuoustimepartialmarkovchainconstructionbyheuristicalgorithmsforpurposeofapproximatetransientanalysis AT tomasruzgas comparisonofcontinuoustimepartialmarkovchainconstructionbyheuristicalgorithmsforpurposeofapproximatetransientanalysis |