We present a novel algorithm to solve a non-linear system of equations, whose solution can be interpreted as a tight lower bound on the vector of expected hitting times of a Markov chain whose transition probabilities are only partially specified. We also briefly sketch how this method can be modified to solve a conjugate system of equations that gives rise to the corresponding upper bound. We prove the correctness of our method and show that it converges to the correct solution in a finite number of steps under mild conditions on the system. We compare the runtime complexity of our method to a previously published method from the literature and identify conditions under which our novel method is more efficient.
Computing Expected Hitting Times for Imprecise Markov Chains
Space Technol.Proceedings
International Conference on Uncertainty Quantification & Optimisation ; 2020 ; Brussels, Belgium November 17, 2020 - November 20, 2020
Advances in Uncertainty Quantification and Optimization Under Uncertainty with Aerospace Applications ; Chapter : 12 ; 185-205
2021-07-16
21 pages
Article/Chapter (Book)
Electronic Resource
English
Computing Expected Hitting Times for Imprecise Markov Chains
TIBKAT | 2021
|An Introduction to Imprecise Markov Chains
Springer Verlag | 2020
|Computing Bounds for Imprecise Continuous-Time Markov Chains Using Normal Cones
Springer Verlag | 2021
|Russian engine hitting performance targets - Delivers slightly more ISP than expected
Online Contents | 1998