Computing Lower and Upper Hitting Probabilities for Imprecise Markov Chains Journal: International Journal of Approximate Reasoning
Marco Sangalli, Rick Reubsaet, Erik Quaeghebeur, Thomas Krak · 2025
Read Computing Lower and Upper Hitting Probabilities for Imprecise Markov Chains Journal: International Journal of Approximate Reasoning by Marco Sangalli, Rick Reubsaet, Erik Quaeghebeur, Thomas Krak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-16696.txt.
Introduction
Marco Sangalli, Erik Quaeghebeur, and Thomas Krak study hitting chances for imprecise Markov chains, where the jump odds are known only as a set of possible matrices. They ask for the lowest and highest chances of ever reaching a target set of states.
First they sort out reachability, since past work used the term in mixed ways, and they map how the rival meanings relate. States then split into those with trivial zero or one chances and those needing real work. For the hard states, the lower chance is the unique fix of a nonlinear equation. Their loop method swaps between solving a linear system and picking an extreme matrix, and converges far faster in tests than worst-case bounds suggest.
Catalog record
| CREATOR | Marco Sangalli, Rick Reubsaet, Erik Quaeghebeur, Thomas Krak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-16696
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computing Lower and Upper Hitting Probabilities for Imprecise Markov Chains Journal: International Journal of Approximate Reasoning Marco Sangalli, Rick Reubsaet, Erik Quaeghebeur, Thomas Krak Abstract We study the computation of lower and upper probabilities of hitting a target set of states for imprecise Markov chains. For these, 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 study the notion of reachability in the imprecise setting. The literature review highlights few different definitions of lower reachability; thus we explore the relations among them, presenting examples to clarify their logical implications. Using this revised definition of reachability for imprecise Markov chain, 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 lower and upper hitting probabilities are the unique solutions of two nonlinear fixed-point equations. 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. 1 Introduction Hitting probabilities play a central role in the analysis of stochastic systems, capturing the likelihood that a process enters a designated set of target states in some finite time. In the classical precise setting of homogeneous Markov chains, these probabilities arise as the minimal nonnegative solution of a linear system and admit a closed-form representation via the fundamental matrix [ 20 , 16 ] . Hitting probabilities can also be regarded as discrete harmonic functions and enjoy a deep analogy with node voltages in potential theory and electrical networks [ 7 ] . In practical applications there is often uncertainty about the transition dynamics, which can be estimated from limited data or elicited from domain experts, yielding a convex set of transition matrices rather than a single, exact one. A natural and rigorous way to represent this kind of epistemic uncertainty is through credal sets – convex sets of probability distributions – leading to the framework of imprecise Markov Chains (IMCs) [ 4 , 13 , 11 ] . In this framework, each row of the transition matrix is specified by a convex set of admissible probability distributions, and the inference quantities of interest are lower and upper hitting probabilities. These bound the true probability of reaching the target states under all compatible transition matrices. These values provide conservative guarantees that are crucial in high-stakes decision-making contexts. They naturally connect to robust control, since they provide worst-case bounds used in min–max robust MDPs under transition uncertainty [ 19 ] , and to stochastic-game formulations, as they correspond to value bounds in zero-sum reachability games [ 2 ] . Our contributions build on the work of Krak et al. [ 17 , 18 ] . They developed characterisations of hitting times and probabilities for IMCs under various model semantics and presented algorithms for computing lower and upper hitting times. We extend this work by (i) discussing and clarifying the definition of reachability in the imprecise setting, (ii) giving a more general characterisation of lower and upper hitting probabilities and (iii) proposing iterative algorithms to compute these quantities. The structure of the paper is as follows. Section 2 introduces the preliminary notions needed for the following sections. In particular, we define hitting probabilities for homogeneous Markov chains, we explain the concept of imprecise Markov chains, and we introduce lower and upper transition operators. Section 3 begins our contributions. There, we formalise the notions of lower and upper reachability in the imprecise setting; we review the different definitions that appear in the literature, clarify the logical relationships between them, and give a few illustrative examples. With these definitions in hand, we isolate those states whose (lower/upper) hitting probabilities are trivial, either zero or one. We then prove that for nontrivial states, lower and upper hitting probabilities are the unique solutions of two nonlinear fixed-point equations. In Section 4 , we turn our attention to developing iterative algorithms to compute lower and upper hitting probabilities. Inspired by the work of Krak et al. [ 18 ] on hitting times, we propose iterative algorithms to compute lower and upper hitting probabilities that alternate between solving a linear system (restricted to a suitable subspace) and selecting an extreme point transition matrix from the credal sets. We rigorously prove their convergence and, in Section 5 , we provide a detailed analysis of their computational cost. We conclude the paper with Section 6 which is dedicated to numerical experiments. Here we show how the theoretical bound on the number of iterations previously established is never attained in practice, and we point out an interesting relation between the density of the graph and the average number of iterations needed for convergence. 2 Preliminaries This section introduces the basic concepts of stochastic processes [ 8 ] , Markov chains [ 20 , 16 ] , hitting probabilities for homogeneous Markov chains [ 20 ] , and imprecise Markov chains [ 4 , 13 , 11 ] . 2.1 Stochastic Processes and Markov Chains Let us denote by \mathbb{N} the set of positive integers and define \mathbb{N}_{0}\coloneqq\mathbb{N}\cup\{0\} . Let \mathcal{X} be a discrete nonempty finite set of cardinality N\in\mathbb{N} and denote by 2^{\mathcal{X}} its power set. Fix an arbitrary ordering over \mathcal{X} : this allows us to identify functions in \mathbb{R}^{\mathcal{X}} and N -dimensional vectors. Define the sample space \Omega\coloneqq\mathcal{X}^{\mathbb{N}_{0}} and endow it with the product \sigma -algebra \mathcal{F}\coloneqq(2^{\mathcal{X}})^{\otimes\mathbb{N}_{0}} , i.e. the \sigma -algebra generated by cylinder sets. A stochastic process (X_{n})_{n\in\mathbb{N}_{0}} is a family of random variables on this measurable space X_{n}:(\Omega,\mathcal{F})\to(\mathcal{X},2^{\mathcal{X}}) where we set X_{n}(\omega)=\omega(n) for all \omega\in\Omega and all n\in\mathbb{N}_{0} [ 8 ] . Let \mathbb{P} be a probability measure on the measurable space (\Omega,\mathcal{F}) , so that (\Omega,\mathcal{F},\mathbb{P}) is a probability space. The probability measure \mathbb{P} determines the law of the stochastic process; in the sequel, we will identify the process with the probability measure \mathbb{P} , which allows us to consider different processes \mathbb{P} over the same measurable space (\Omega,\mathcal{F}) [ 17 ] . A stochastic process \mathbb{P} is said to be a Markov chain if it satisfies the Markov property: \mathbb{P}(X_{n+1}=x_{n+1}\mid X_{0:n}=x_{0:n})=\mathbb{P}(X_{n+1}=x_{n+1}\mid X_{n}=x_{n}) (1) for all x_{0},\dots,x_{n},x_{n+1}\in\mathcal{X} and all n\in\mathbb{N}_{0} . This property is often interpreted as the process being memoryless; the transition probabilities depend only on the current state, and any previous history is not relevant. A Markov chain \mathbb{P} is said to be (time-) homogeneous if \mathbb{P}(X_{n+1}=x\mid X_{n}=y)=\mathbb{P}(X_{1}=x\mid X_{0}=y) (2) for all x,y\in\mathcal{X} and for all n\in\mathbb{N}_{0} . A matrix T\in\mathbb{R}^{N\times N} is called a transition matrix if it satisfies 1. T(x,y)\geq 0 for all x,y\in\mathcal{X} , and 2. \displaystyle\sum_{y\in X}T(x,y)=1 for all x\in\mathcal{X} . Note that each row T(x,\cdot) of a transition matrix is a probability mass function on \mathcal{X} . Every transition matrix T uniquely determines a homogeneous Markov chain \mathbb{P}_{T} up to its initial distribution, by setting \mathbb{P}_{T}(X_{n+1}=x\mid X_{n}=y)=T{(x,y)} (3) for all x,y\in\mathcal{X} and for all n\in\mathbb{N}_{0} . Thus, transition matrices