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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Computing Expected Hitting Times for Imprecise Markov Chains


    Additional title:

    Space Technol.Proceedings


    Contributors:

    Conference:

    International Conference on Uncertainty Quantification & Optimisation ; 2020 ; Brussels, Belgium November 17, 2020 - November 20, 2020



    Publication date :

    2021-07-16


    Size :

    21 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English