Computing lower and upper hitting probabilities for imprecise Markov chains

Read full text Summarise with VIRAT
Authors: Marco Sangalli, Rick Reubsaet, Erik Quaeghebeur, Thomas Krak
Cited by: 0
References: 21

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

• Clarified lower and upper reachability definitions for IMCs and their relations • Lower hitting probabilities as unique solution of nonlinear fixed-point equation • Efficient iterative algorithms to compute lower and upper hitting probabilities We study the computation of lower and upper probabilities of hitting a target set of states for imprecise Markov chains, where transition uncertainty is modelled by a convex set of transition matrices. In the precise case, hitting probabilities are the minimal nonnegative solution of a linear system and admit a closed-form expression. We investigate the notion of reachability in the imprecise setting. The literature review highlights several different definitions of lower reachability; thus, we explore the relations among them and present examples to clarify their logical implications. Using this revised definition of reachability for imprecise Markov chains, we partition the state space into classes of states whose hitting probabilities are trivially zero or one, and those which require further computation. For these nontrivial states, we show that the lower hitting probability is the unique solution of a nonlinear fixed-point equation, while the same does not hold for upper hitting probabilities. For the practical computation of lower and upper hitting probabilities, we propose iterative algorithms that alternate between solving a linear system and choosing an extreme point from the set of transition matrices. Numerical experiments demonstrate that, in practice, these algorithms converge in substantially fewer iterations than the theoretically established worst-case bound.

Fields of Study & Subjects

Formal Methods in Verification Bayesian Modeling and Causal Inference Logic Reasoning and Knowledge

Publication details

Journal / source
International Journal of Approximate Reasoning
Volume
194
Pages
109671–109671
Publication date
24 March 2026
Language
EN