betaFeedback

WorksComputer Science

Path Abstraction for Markov Reward Models: An Isabelle Formalisation in a Free Monoid View

Abstract

The classical definition of discrete-time Markov chains maps pairs of states to transition probabilities. An alternative, proposed in the context of path abstraction in probabilistic counterexample refinement, is to view them as a transition kernel on the free monoid on the state space, mapping paths directly to path probabilities. In this paper, we first extend the free monoid view and path abstraction algorithm to cumulative rewards on Markov reward models. We then use Isabelle/HOL to formalise Markov chains and reward models in this view, exploiting the discrete finite-prefix semantics to work with Isabelle's standard HOL-Analysis library. We mechanise the path abstraction algorithm and its key correctness properties of well-definedness and monotonic absorption, establishing the preservation of reachability probabilities and expected rewards. Proving the convergence of these quantities on relevant path sets is aided by our use of the lightweight free monoid semantics in place of the standard measure-theoretic one used in established Isabelle formalisations of Markov models. We obtain a verified abstract implementation of path abstraction in Isabelle/HOL, providing a foundation for refinement to efficient executable code and integration with probabilistic model checkers.

Introduction

Markov chains and reward models are the basic formalisms to model probabilistic reactive systems, widely used in dependability and performance evaluation [5]. They also provide the semantics for various probabilistic programming languages [8]. Efficient tools use probabilistic and statistical model checking [3, 4, 7] to check properties of interest, e.g. to determine whether ϕ≤pG\phi^G_{\le p}—a PCTL [9] formula asking whether the probability to reach a certain subset GG of goal states is at most some threshold pp—or to find a lower bound on E(◊G)\mathbb{E}(\Diamond G), the expected reward (e.g. runtime cost) accumulated before reaching GG. In this paper, we specifically focus on probabilistic model checking (PMC) for (time-homogeneous) discrete-time Markov chains (DTMCs) and Markov reward models (MRMs) given probabilistic reachability properties like ϕ≤pG\phi^G_{\le p} or expected reward queries for E(◊G)\mathbb{E}(\Diamond G).

A DTMC is a stochastic process {Xt}t∈T\{X_t\}_{t\in T} over a discrete state space SS and (time) index set T=NT=\mathbb{N} that satisfies the Markov (memoryless) property. An MRM adds a random variable mapping paths to real values. DTMCs are classically defined via their transition kernel or probability matrix, that is, the one-step probabilities P(Xi+1=t∣Xi=s)\mathbf{P}(X_{i+1}=t \mid X_i=s) of moving from state ss to tt for all pairs of states, plus an initial state or initial distribution. An MRM then additionally provides one-step reward values. DTMCs and MRMs have been formalised in Isabelle/HOL in this view [12, 13, 18], starting from a Markov kernel upon which probability measures on sets of (infinite) paths or traces, expectations, etc. can be built.

When a non-probabilistic model checker finds that a property does not hold, its verdict is accompanied by a counterexample, typically one path through the model. In PMC, the notion of counterexample is more involved: If ϕ≤pG\phi^{G}_{\leq p} does not hold, then a counterexample could be a set of paths, each of which reaches GG from the initial state, and which in total has a probability mass greater than pp. These sets can quickly grow too large to be helpful in explaining the PMC result to the user, or to help them correct their model or system. Various other high- and low-level notions of probabilistic counterexamples have thus been developed over the past two decades [1]—in essence, various ways of representing sets of paths in compact and explainable ways. Among these, we are interested in techniques that abstract the DTMCs we analyse in a refined manner, and in particular the path abstraction approach coined by Ábrahám et al. in 2010 [2].

Path abstraction can be seen as both a PMC algorithm and a counterexample refinement approach: In the case of ϕ≤pG\phi^{G}_{\leq p} not holding, the set of all paths that reach GG is a counterexample, and is what PMC algorithms usually (implicitly) compute. Yet as a witness to the violation of the threshold, a much smaller set may be sufficient. Path abstraction provides a heuristic to structurally find these smaller subsets of the (total) path sets, by iteratively abstracting the DTMC over a sequence of subsets of S−GS-G, the set of non-goal states. Notably, performing path abstraction over S−GS-G directly is equivalent to PMC, and provides no refined diagnostic information; the contribution of path abstraction arises from the use of a well-chosen sequence of such abstraction sets.

State of the art. Path abstraction was originally formulated for DTMCs only [2], using their classical definition, and tightly coupled to a decomposition into strongly connected components (SCCs) determining the sequence of abstraction sets. In 2025, we proved that any sequence of subsets of S−GS-G can be chosen to abstract the DTMC [10]. They also showed the two crucial correctness properties, which had not been explicitly addressed in [2]: (1) Path-abstracting a DTMC yields another DTMC (well-definedness [10 Lemma 2]), and (2) path-abstracting a DTMC over a set of states AA and then over a set of states B⊇AB \supseteq A yields the same result as abstracting over BB straight away (monotonic absorption [10 Thm. 3]).

Both (1) and (2) were proven in a free monoid view of DTMCs: instead of the classical transition kernel S×S→[0,1]S \times S \to[0,1], they use one of the form S∗→[0,1]S^* \to[0,1] where S∗S^* is the free monoid on SS (i.e. the set of words over alphabet SS), enabling smoother correctness proofs (notably for monotonic absorption). However, the proofs of [10] still fill ≈6\approx6 densely written pages in the paper’s extended version [11 App. A & B] solely relying on the trust level of human-brain reasoning.

Our contributions. We put the work of [10] onto a formal, machine-checked foundation, and simultaneously extend it to MRMs: (i) We define MRMs in the free monoid view, and specify a new path abstraction algorithm for MRMs that preserves expected (cumulative) rewards. (ii) We formalise MRMs and DTMCs, and the two corresponding path abstraction algorithms, in Isabelle/HOL. (iii) For both algorithms, we mechanise well-definedness and monotonic absorption.

We thus provide machine-checked correctness proofs for counterexample refinement at the trust level of the Isabelle inference kernel. For DTMC reachability, we build on the definitions and pen-and-paper proofs of [11]; for expected rewards on MRMs, we provide the first free monoid-based definition and path abstraction algorithm, with completely new proofs made directly in Isabelle/HOL. We also make explicit how path-abstracting over the non-goal states is equivalent to PMC, preserving reachability probabilities and expected rewards—which was stated but not proven in [10].

Our work emphasises how an appropriate choice of representation—based on an a-priori introspection to identify the minimal semantics/theory in which a problem (and its proofs) can be expressed—can significantly reduce the effort to apply interactive theorem proving (ITP). Concretely, Isabelle/HOL’s semantic framework around lists combines very naturally with the algebraic and list-recursive nature of the path abstraction algorithms. The free monoid view additionally simplified our proof setup: Where general formalisations like Hölzl’s capture the classical probability space for a DTMC induced by the cylinder sets of all possible paths, we only look at the set of minimal paths (or words) w.r.t. the prefix order, thus taking a basis of that induced σ\sigma-algebra and circumventing having to reason about σ\sigma-algebras in the first place. Path abstraction is then merely a discrete mathematics operation. Where we need measure-theoretic reasoning, we draw on the HOL-Analysis library, at most having to prove a special case of Tonelli’s theorem [17 Sec. 20.1] for double infinite sums. Connecting the representations, we show the correspondence between the classical and free monoid views in § 3. Overall, the most conceptually involved (and time-consuming) part of our proofs was to show that reachability probabilities and expected rewards converge (Thms. 5.1 and 5.3, see Remark 4.3), which are essential conditions enabling the proofs of our main lemmas. To the best of our knowledge, no similar statement has been shown using ITP in a semantics this lightweight for Markov models.

Outline. We recall, in Sects. 2 and 3, theory on free monoids and real analysis, then define MRMs and DTMCs in both the classical and free monoid views. § 4 introduces path abstraction and relates it to PMC. We then present our formalisation and mechanisation of MRMs, path abstraction, and the corresponding Isabelle/HOL proofs in § 5.

Preliminaries

Let N={0,1,2,…}\mathbb{N} = \{0,1,2,\ldots\} denote the set of natural numbers, and N+=N−{0}\mathbb{N}^{+} = \mathbb{N} - \{0\} the set of positive integers. For a set SS, we let 2S≡{S′∣S′⊆S}2^{S} \equiv\{S' \mid S' \subseteq S\} denote its power set. Given a function f:X→Yf: X \to Y and a set Y′⊆YY' \subseteq Y, we denote by f−1(Y′)≡{x∈X:f(x)∈Y′}f^{-1}(Y') \equiv\{x \in X: f(x) \in Y'\} the pre-image of Y′Y' under ff. The universal set is denoted by U\mathbb{U} and is the equivalent of Isabelle’s UNIV.

Languages and the Free Monoid

Given a set SS, we let S∗S^{*} denote the set of all words that have letters in alphabet SS, and let ε\varepsilon denote the empty word. S∗S^{*} is called the free monoid on SS, and is indeed a monoid with the empty word ε\varepsilon as neutral element and concatenation of words as (an associative) binary operation on S∗S^{*}. Let S+S^{+} denote the Kleene plus of SS: S+≡S∗−{ε}S^{+} \equiv S^{*} - \{\varepsilon\}. The concatenation of two words xx and yy is denoted by xyxy. Given a word xx, we let set⁡(x)\operatorname{set}(x) denote the smallest subset of SS containing the letters of xx, i.e. set⁡(x)=⋂A⊆S:x∈A∗A\operatorname{set}(x) = \bigcap_{A \subseteq S: x \in A^{*}} A. Note that set⁡(x)\operatorname{set}(x) is finite. Given x,y∈S∗x,y \in S^{*} we say that yy is a prefix of xx, denoted by y≤xy \leq x, if there exists a word zz such that x=yzx = yz. Then, ≤\leq becomes a partial order on S∗S^{*}, called the prefix order. We say that yy is a factor of xx, denoted by y⊑xy \sqsubseteq x, if there exist words w,zw,z such that x=wyzx = wyz; we let ∣x∣y≡∣{(w,z)∈S∗×S∗:x=wyz}∣|x|_{y} \equiv|\{(w,z) \in S^{*} \times S^{*}: x = wyz\}| denote the number of factor occurrences of yy in $x. For x∈S∗x \in S^{*}, we let ∣x∣|x| denote the length of xx. Note that ∣x∣=∑a∈set⁡(x)∣x∣a|x| = \sum_{a \in\operatorname{set}(x)} |x|_{a}.

Let Sω={s0s1s2…:∀i∈N.si∈S}S^{\omega} = \{s_{0}s_{1}s_{2}\ldots: \forall i \in\mathbb{N}. s_{i} \in S\} denote the set of all infinite sequences over SS. Note that one can concatenate a word over SS with an infinite sequence over SS, and that a word over SS can be a prefix of an infinite sequence over SS.

A set LL is called a language over the alphabet SS if L⊆S∗L \subseteq S^{*}, and we let L⊥≡{x∈L:x′∈L∧x′≤x⇒x′=x}L_{\bot} \equiv\{x \in L: x' \in L \land x' \leq x \Rightarrow x' = x\} denote the prefix-minimal part of LL. Note that (L⊥)⊥=L⊥(L_{\bot})_{\bot} = L_{\bot}.

The concatenation of two languages K,L⊆S∗K,L \subseteq S^{*} is denoted by KLKL and is defined by KL≡{xy:x∈K∧y∈L}KL \equiv\{xy: x \in K \land y \in L\}. Furthermore, the prefix order ≤\leq on S∗S^{*} extends to languages K,L⊆S∗K,L \subseteq S^{*}: we write K≤LK \leq L if ∀x∈L. ∃y∈K. y≤x\forall x \in L.\ \exists y \in K.\ y \leq x. Note that ≤\leq is a pre-order on 2S∗2^{S^{*}} but not a partial order (any two distinct languages containing ε\varepsilon precede each other w.r.t. ≤\leq).

Whenever convenient, we interpret single symbols as words and words as singleton languages, and omit set brackets around words when referring to singleton languages.

Finally, given x∈S∗x \in S^{*} we let ⋆x\star x denote the tail of xx, where ⋆x≡ε\star x \equiv\varepsilon if x=εx = \varepsilon and ⋆x≡x′\star x \equiv x' if x=ax′x = ax' for some a∈Sa \in S and x′∈S∗x' \in S^{*}. The ⋆\star-operator extends to languages through ⋆L≡{⋆x:x∈L}\star L \equiv\{\star x: x \in L\} (where L⊆S∗L \subseteq S^{*}), and can hence also be used as the binary operation on 2S∗2^{S^{*}} where K⋆L=K(⋆L)K \star L = K(\star L).

Infinite Sums and Real Analysis

To reason with probability masses of infinite sets of paths, which are unordered infinite sums1 of individual path probabilities, we default to the following definition of infinite sums, which is also the standard definition in HOL-Analysis:

Definition 2.1. Let f:A→Rf : A \to\mathbb{R} and L∈RL \in\mathbb{R}. Then ff has infinite sum LL on AA, denoted ∑x∈Af(x)=L\sum_{x\in A} f(x) = L, if

∀ϵ>0. ∃F. F⊆A∧∣F∣<∞∧ ∀F′. F⊆F′⊆A∧∣F′∣<∞⟹∣∑x∈F′f(x)−L∣<ϵ.(1)\begin{aligned} &\forall\epsilon> 0.\ \exists F.\ F \subseteq A \land|F| < \infty\\ &\land\ \forall F'.\ F \subseteq F' \subseteq A \land|F'| < \infty\Longrightarrow\left|\sum_{x\in F'} f(x)-L\right| < \epsilon. \tag*{(1)} \end{aligned}

That is, ∑x∈Af(x)=L\sum_{x\in A} f(x) = L if relative to every positive error tolerance there exists a finite subset FF of AA such that we can approximate LL by summing ff over any finite subset of AA containing FF.2 Eq. (1) is trivially satisfied if AA itself is finite.

Markov Chains and Reward Models

Definition 2.2. A (transition-based) Markov reward model (MRMMRM) is a tuple M=(S,s0,P,R)\mathcal{M} = (S, s_0, \mathbf{P}, R) with finite state space SS, initial state s0∈Ss_0 \in S, transition probability function P:S×S→[0,1]\mathbf{P}: S \times S \to[0,1] with ∀s∈S. ∑t∈SP(s,t)=1\forall s \in S.\ \sum_{t\in S}\mathbf{P}(s,t) = 1, and reward function R:S×S→RR: S \times S \to\mathbb{R} s.t. P(s,t)=0⇒R(s,t)=0\mathbf{P}(s,t) = 0 \Rightarrow R(s,t) = 0.

Definition 2.3. A discrete-time Markov chain (DTMCDTMC) is a triple M=(S,s0,P)M = (S,s_0,\mathbf{P}) such that S,s0,PS,s_0,\mathbf{P} are the first three entries of an MRMMRM.

Given an MRMMRM M=(S,s0,P,R)\mathcal{M} = (S,s_0,\mathbf{P},R), we call (S,s0,P)(S,s_0,\mathbf{P}) its underlying or induced DTMCDTMC. A DTMCDTMC M=(S,s0,P)M = (S,s_0,\mathbf{P}) further induces a directed graph (S,E)(S,E) with edge set E={(s,t)∈S×S:P(s,t)>0}E = \{(s,t) \in S \times S : \mathbf{P}(s,t) > 0\}, called the underlying graph of MM, which can also be seen as the underlying graph of M\mathcal{M}.

To a DTMCDTMC M=(S,s0,P)M = (S,s_0,\mathbf{P}) we can associate the sets M+⊆S+M^+ \subseteq S^+ and Mω⊆SωM^\omega\subseteq S^\omega of finite and infinite paths of its underlying graph, including paths that do not contain edges but just consist of a single state. Both give rise to the following probability space on MM standard in the literature:

Theorem 2.1. Let F\mathcal{F} be the σ\sigma-algebra on MωM^\omega generated3 by the set {xSω∩Mω:x∈M+}⊆2Sω\{xS^\omega\cap M^\omega: x \in M^+\} \subseteq2^{S^\omega}. Then, there exists a unique function μ:F→[0,1]\mu: \mathcal{F} \to[0,1] satisfying, for all x∈M+x \in M^+,

μ(xSω∩Mω)={P(x),if x=x0…xn∧x0=s0∧n>0,1,if x=s0,0,otherwise,(2)\mu(xS^\omega\cap M^\omega) = \begin{cases} \mathbf{P}(x), & \text{if } x = x_0 \ldots x_n \land x_0 = s_0 \land n > 0,\\ 1, & \text{if } x = s_0,\\ 0, & \text{otherwise,} \end{cases} \tag*{(2)}

such that (Mω,F,μ)(M^\omega,\mathcal{F},\mu) is a probability space, where P(x)\mathbf{P}(x) is short for

∏i=0n−1P(xi,xi+1)\prod_{i=0}^{n-1} \mathbf{P}(x_i,x_{i+1})

in the first case of (2).

Proof. Argued in (the context of) [6 Def. 10.10]. ⊓⊔\sqcap\sqcup

Definition 2.4. Given a set G⊆SG \subseteq S of goal states, the unbounded reachability probability of reaching GG in MM is

P(◊G)≡μ(Mω−(S−G)ω).(3)\mathbf{P}(\Diamond G) \equiv\mu\left(M^\omega- (S-G)^\omega\right). \tag*{(3)}

Convention 1. We assume throughout that any set of goal states does not contain the initial state. We do this because in the case s0∈Gs_0 \in G we trivially have P(◊G)=1\mathbf{P}(\Diamond G)=1, and there would be nothing substantial left to compute or to reason with.

Remark 2.1. Note that Mω−(S−G)ωM^\omega-(S-G)^\omega is the set of all paths in MM that contain a state in GG, and that

Mω−(S−G)ω=⋃˙x∈M+∩(S−G)∗GxSω∩Mω(4)M^\omega-(S-G)^\omega=\mathop{\mathbin{\dot{\bigcup}}}_{x\in M^+\cap(S-G)^*G}xS^\omega\cap M^\omega \tag*{(4)}

is a disjoint4 countable union of sets that are measurable by definition of F\mathcal{F} in Thm. 2.1 and hence is itself measurable. As such, (3) is well-defined.

Definition 2.5. Let M=(S,s0,P,R)\mathcal{M}=(S,s_0,\mathbf{P},R) be an MRM. Then, given a set G⊆SG\subseteq S of goal states, the expected reward of reaching GG in M\mathcal{M} is defined by

E(◊G)≡E[X]=∫MωX(x) dμ(x)(5)\mathbb{E}(\Diamond G)\equiv\mathbb{E}[X]=\int_{M^\omega}X(x)\,d\mu(x) \tag*{(5)}

where E[X]\mathbb{E}[X] is the expected value of the random variable X:Mω→RX:M^\omega\to\mathbb{R} defined by, where we write x=x0x1…x=x_0x_1\ldots,

X(x)≡{∑i=0n−1R(xi,xi+1)if x∈Mω−(S−G)ω∧x0…xn−1∈(S−G)∗∧xn∈G,0otherwise.(6)X(x)\equiv \begin{cases} \sum_{i=0}^{n-1}R(x_i,x_{i+1}) & \text{if }x\in M^\omega-(S-G)^\omega\\ & \qquad\land x_0\ldots x_{n-1}\in(S-G)^*\land x_n\in G,\\ 0 & \text{otherwise.} \end{cases} \tag*{(6)}

Remark 2.2. Note that nn in (6) exists as an element of N\mathbb{N} and is unique if x∈Mω−(S−G)ωx\in M^\omega-(S-G)^\omega, with the conventions that the sum and the second clause of the condition of the first case of (6) are zero and vacuous, respectively, in the case n=0n=0. Note furthermore that XX in Def. 2.5 is indeed a random variable, as the image X(Mω)⊆RX(M^\omega)\subseteq\mathbb{R} of MωM^\omega under XX is countable and the inverse image of every real number under XX is a countable union of the basis sets xSω∩MωxS^\omega\cap M^\omega (where x∈M+x\in M^+) of the σ\sigma-algebra F\mathcal{F} from Thm. 2.1, together with possibly Mω∩(S−G)ωM^\omega\cap(S-G)^\omega, whose measurability is seen through

Mω∩(S−G)ω=⋂n∈N⋃x∈M+∩(S−G)n+1xSω∩Mω,(7)M^\omega\cap(S-G)^\omega=\bigcap_{n\in\mathbb{N}}\bigcup_{x\in M^+\cap(S-G)^{n+1}}xS^\omega\cap M^\omega, \tag*{(7)}

which is a countable intersection of countable unions of basis sets xSω∩MωxS^\omega\cap M^\omega of the σ\sigma-algebra F\mathcal{F} from Thm. 2.1, hence measurable.

Markov Models in Isabelle/HOL

The notions of MRMs and DTMCs have been formalised in Isabelle, most notably by Hölzl et al. [13], who formalise a DTMC as a transition kernel mapping a state to a discrete probability distribution indexed by its successor states. In their formalisation, reachability probabilities are defined as the measure of the event in the trace space that eventually the goal set is reached. The trace space’s sample space is the set of all infinite sequences over the state space—hence possibly including those of zero probability—with a σ\sigma-algebra and measure generated and defined analogously to those in Thm. 2.1. Expected rewards in [13] are expressed as least fixpoints of a functional that sums up state pair rewards until the set of goal states is reached, and hence only admit non-negative rewards; more recent work extends to rewards with arbitrary real values [18].

A Free Monoid View on Markov Models

For reasoning about reachability probabilities in DTMCs with finite state spaces, a lightweight semantics that does not involve measure theory suffices [10]; the same holds for expected rewards in MRMs. The quantities of interest P(◊G)\mathrm{P}(\Diamond G) in (3) and E(◊G)\mathrm{E}(\Diamond G) in (5) can be expressed as infinite sums over finite paths. In the setting of Thm. 2.1 and Defs. 2.4 and 2.5, this is reflected in the following result.

Theorem 3.1. For an MRM M=(S,s0,P,R)\mathcal{M} = (S, s_0, P, R), we have

P(◊G)=∑x∈s0(S−G)∗GP(x),E(◊G)=∑x∈s0(S−G)∗GP(x)R(x),(8)\begin{aligned} \mathrm{P}(\Diamond G) &= \sum_{x \in s_0(S-G)^{*}G} \mathrm{P}(x),\\ \mathrm{E}(\Diamond G) &= \sum_{x \in s_0(S-G)^{*}G} \mathrm{P}(x)R(x), \tag*{(8)} \end{aligned}

where P(x)\mathrm{P}(x) is short for ∏i=0n−1P(xi,xi+1)\prod_{i=0}^{n-1} \mathrm{P}(x_i, x_{i+1}) for x=x0…xnx = x_0 \ldots x_n and n∈N+n \in\mathbb{N}^{+}, as written earlier in Thm. 2.1, and, analogously, R(x)R(x) is short for ∑i=0n−1R(xi,xi+1)\sum_{i=0}^{n-1} R(x_i, x_{i+1}).

Proof of Thm. 3.1. For P(◊G)\mathrm{P}(\Diamond G), we use (3) and (4) and the countable additivity rule of measures to deduce that P(◊G)=∑x∈M+∩(S−G)∗Gμ(xSω∩Mω)\mathrm{P}(\Diamond G) = \sum_{x \in M^{+} \cap(S-G)^{*}G} \mu(xS^{\omega} \cap M^{\omega}). Note that μ(xSω∩Mω)=P(x)\mu(xS^{\omega} \cap M^{\omega}) = \mathrm{P}(x) for each x∈M+∩(S−G)∗Gx \in M^{+} \cap(S-G)^{*}G by (2), and hence P(◊G)=∑x∈M+∩(S−G)∗GP(x)\mathrm{P}(\Diamond G) = \sum_{x \in M^{+} \cap(S-G)^{*}G} \mathrm{P}(x). Since μ(xSω∩Mω)=0\mu(xS^{\omega} \cap M^{\omega}) = 0 if x∈S+x \in S^{+} does not start in s0s_0, we can replace the domain M+∩(S−G)∗GM^{+} \cap(S-G)^{*}G by M+∩(S−G)∗G∩s0S∗M^{+} \cap(S-G)^{*}G \cap s_0S^{*}. Since s0∉Gs_0 \notin G by Conv. 1, we have (S−G)∗G∩s0S∗=s0(S−G)∗G(S-G)^{*}G \cap s_0S^{*} = s_0(S-G)^{*}G. Then, we obtain P(◊G)=∑x∈M+∩s0(S−G)∗GP(x)\mathrm{P}(\Diamond G) = \sum_{x \in M^{+} \cap s_0(S-G)^{*}G} \mathrm{P}(x), and, given that P(x)=0\mathrm{P}(x) = 0 for all x∈S+−M+x \in S^{+} - M^{+} by definition of M+M^{+}, P(◊G)=∑x∈s0(S−G)∗GP(x)\mathrm{P}(\Diamond G) = \sum_{x \in s_0(S-G)^{*}G} \mathrm{P}(x), and we have verified the first line of (8).

For E(◊G)\mathrm{E}(\Diamond G), starting from (6), we note that the random variable XX encoding RR on finite paths is constant on each basis set xSω∩MωxS^{\omega} \cap M^{\omega} (x∈M+x \in M^{+}) of the σ\sigma-algebra of the probability space on MM (it is constant with value R(x)R(x) or with value $0), and hence its expected value is the sum of all involved path probabilities multiplied by their respective cumulative rewards. By this argument, given that we have established the first line of (8), its second line follows. □\square

We later show that the two sums of (8) in fact converge: this is Thm. 5.1 for probabilities, and follows from Thm. 5.3 for expected rewards.

So far, for convenience, we have used P(x)\mathbf{P}(x) and R(x)R(x) as abbreviations of the probability and (cumulative) reward of a path xx. Since we need to reason a lot with path probabilities and cumulative rewards, we adopt the free monoid view of [10], which defines DTMCs via probabilities of all non-empty words over the state space, and extend it to MRMs. Since we have defined DTMCs as structures underlying MRMs in Def. 2.2, we only need to rework this exact definition.

Definition 3.1 (MRM in a free monoid view). A Markov reward model (MRM) is a quadruple M=(S,s0,P,R)\mathcal{M}=(S,s_0,\mathbf{P},R) where SS is a finite set called the state space of M\mathcal{M}; s0∈Ss_0 \in S is the initial state of M\mathcal{M}; P:S+→[0,1]\mathbf{P}:S^{+}\to[0,1] is a function satisfying, for all s∈Ss\in S, ∑t∈SP(st)=1\sum_{t\in S}\mathbf{P}(st)=1 and P(s)=1\mathbf{P}(s)=1 and x,y∈S∗⇒P(xsy)=P(xs)P(sy)x,y\in S^{*}\Rightarrow\mathbf{P}(xsy)=\mathbf{P}(xs)\mathbf{P}(sy); and R:S+→RR:S^{+}\to\mathbb{R} is a function satisfying R(x)=0R(x)=0 whenever ∣x∣=1∨P(x)=0\lvert x\rvert=1\lor\mathbf{P}(x)=0 and, for all s∈Ss\in S and x,y∈S∗x,y\in S^{*} for which P(xsy)>0\mathbf{P}(xsy)>0, R(xsy)=R(xs)+R(sy)R(xsy)=R(xs)+R(sy).

The above definition captures the fact that the function P\mathbf{P} must mimic a probability distribution per state indexed by its successor states via two-state sequences; the Markov property is captured by the rule that we can break down a path at any point such that the probability of the whole path equals the product of the probabilities of the two segments. Furthermore, the cumulative reward function’s cumulative property—namely, on a path with non-zero probability, its cumulative reward is the sum of the rewards of the transitions on the path—is captured by a similar rule of breaking a path into two segments; finally, (cumulative) rewards on paths that consist of a single state or have probability zero must be zero as well.

Remark 3.1. The correspondence between MRMs in the classical view of Def. 2.2 and MRMs in the free monoid view of Def. 3.1 can be seen as follows. By the rule in Def. 3.1 that P(xsy)=P(xs)P(sy)\mathbf{P}(xsy)=\mathbf{P}(xs)\mathbf{P}(sy) for all s∈Ss\in S and x,y∈S∗x,y\in S^{*}, the function P\mathbf{P} is fully determined by its values on two-state sequences. A similar argument applies to the reward function.

Convention 2. Within PMC, the condition ∑t∈SP(st)=1\sum_{t\in S}\mathbf{P}(st)=1 for all s∈Ss\in S in Def. 3.1 is often too strict and hence relaxed to ∑t∈SP(st)≤1\sum_{t\in S}\mathbf{P}(st)\le1 for all s∈Ss\in S. From now on, we adopt this convention.

In the free monoid view of MRMs, P(◊G)\mathbf{P}(\Diamond G) and E(◊G)\mathop{\mathbb{E}}(\Diamond G) are defined directly by (8), which Thm. 3.1 relates back to the original Defs. 2.4 and 2.5 in the classical view. From now on, we work in the free monoid view exclusively.

Path Abstraction and PMC

In this section, we illustrate path abstraction with an example, restate its definition for DTMCs, and extend it to MRMs. We then show that abstracting over all non-goal states yields reachability probabilities and expected rewards exactly, while intermediate abstractions can already provide bounds that suffice to decide whether a threshold is met. The mechanised proofs are included in our supplementary material (file supplementary-material.zip), and we refer to the specific files for each theorem from now on.

Motivating Example

Let us motivate our interest in the path abstraction technique with the example program in Figure 1, which contains a fair coin flip.

A probabilistic program

Figure 1. A probabilistic program

We can model the behaviour of this program as a DTMC by composing a state space of all possible values the pair (x,y)(x, y) of variables can take, where an undefined division is indicated with a +∞+\infty-sign:

S={(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(2,2),(2,∞)}.(9)S = \{(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (2, \infty)\}. \tag*{(9)}

Here, the initial state is (0,0)(0, 0). Additionally, we would like to capture the (expected) time it takes to reach a terminal state. Suppose that a +1+1-increment, doubling, and additive inversion take 1 time unit each, and multiplicative inversion takes 2 time units. We can now model the program in Figure 1 with these computation time costs as a transition-based reward function into a full MRM, shown in Figure 2.

The MRM of Fig. 1 with computation times

Figure 2. The MRM of Figure 1 with computation times

Now, let us illustrate the path abstraction technique [2, 10]. Suppose we only want to run our program if P(◊(2,∞))≤15%\mathrm{P}(\Diamond(2, \infty)) \le15\%. Rather than computing this probability exactly, we want to find a lower bound that exceeds 15% to conclude that we shall not run our program. To this end, let us consider the sub-MRM “induced” by A={(1,0),(1,1)}A = \{(1, 0), (1, 1)\}, with state space AA together with the states outside of AA that can be reached from AA within one step as terminal states. Figure 3 shows AA in grey and the sub-MRM within dotted lines.

MRM of Fig. 1 with sub-MRM induced by A = {(1, 0), (1, 1)}

Figure 3. The MRM of Figure 1 with sub-MRM induced by A={(1,0),(1,1)}A = \{(1,0),(1,1)\}

Now, in this sub-MRM, we reroute the total reachability probabilities and expected rewards (divided by the respective reachability probabilities) onto new transitions from the states of AA from which one can reach an outside state (in this case all of AA) to those outside states. The result is shown in Figure 4.

MRM abstracted over A into a new MRM

Figure 4. The MRM abstracted over AA into a new MRM

Here, the abstract path x=(0,0)(1,0)(2,1)(2,∞)x = (0, 0)(1, 0)(2, 1)(2, \infty) has probability 16\frac{1}{6}, which is greater than 15%. Since path abstraction preserves5 reachability probabilities, we have P(◊(2,∞))=P′(◊(2,∞))\mathbf{P}(\Diamond(2,\infty)) = \mathbf{P}'(\Diamond(2,\infty)) where P\mathbf{P} and P′\mathbf{P}' are the transition probability functions of the MRMs of Figure 2 and Figure 4, respectively. Clearly, P′(x)=16\mathbf{P}'(x) = \frac{1}{6} contributes to the sum constituting P′(◊(2,∞))\mathbf{P}'(\Diamond(2,\infty))—see Thm. 3.1—and thus P(◊(2,∞))=P′(◊(2,∞))≥16>15%\mathbf{P}(\Diamond(2,\infty)) = \mathbf{P}'(\Diamond(2,\infty)) \ge\frac{1}{6} > 15\%, and we do not run our program. Note that P(◊(2,∞))>15%\mathbf{P}(\Diamond(2,\infty)) > 15\% was not deducible in the analogous manner from a single path in the original MRM in Figure 2, as the largest probability of a path from (0,0)(0,0) to (2,∞)(2,\infty) is 18=12.5%<15%\frac{1}{8} = 12.5\% < 15\%.

We can also obtain information about other quantities of interest. For example, summing probability times reward over the two paths (0,0)(1,0)(2,0)(2,2)(0,0)(1,0)(2,0)(2,2) and (0,0)(0,1)(1,1)(2,1)(2,∞)(0,0)(0,1)(1,1)(2,1)(2,\infty) in Figure 4 yields

13⋅(1+73+5)+16⋅(2+1+73+5)=92(10)\frac{1}{3}\cdot\left(1+\frac{7}{3}+5\right)+\frac{1}{6}\cdot\left(2+1+\frac{7}{3}+5\right)=\frac{9}{2} \tag*{(10)}

which serves as a lower bound of E(◊{(2,2),(2,∞)})\mathbb{E}(\Diamond\{(2,2),(2,\infty)\}).

The Path Abstraction Algorithms

We now restate the definition of path abstraction for DTMCs [2] in the free monoid view [10 Def. 6]. To this end, we fix a DTMC M=(S,s0,P)M=(S,s_0,\mathbf{P}) in the free monoid view, as defined in Def. 3.1, with the relaxed substochasticity convention Conv. 2.

Definition 4.1. Given L⊆S+L \subseteq S^+, let P(L)\mathbf{P}(L) denote the infinite sum

P(L)≡∑x∈L⊥P(x),(11)\mathbf{P}(L) \equiv\sum_{x\in L_\perp}\mathbf{P}(x), \tag*{(11)}

where we recall that L⊥L_{\perp} is the set of minimal elements of LL with respect to the prefix order ≤\le.

In (11) we mostly focus on those LL of the form L=aL′L = aL' with a∈Sa \in S and L′⊆S∗L' \subseteq S^*. Then, the interpretation of P(L)\mathbf{P}(L) is that it is the probability that an infinite trajectory starting in state aa initially moves along a path in LL. Indeed: this probability is equal to the measure of the union of all basis sets xSω∩MωxS^\omega\cap M^\omega where xx ranges over LL (where the σ\sigma-algebra involved is taken w.r.t. initial state aa), which can be written as the disjoint union of all xSω∩MωxS^\omega\cap M^\omega where xx ranges over the prefix-minimal part L⊥L_{\perp} of LL—i.e. all minimal elements of LL w.r.t. the prefix order—because x≤x′x \le x' always implies x′Sω∩Mω⊆xSω∩Mωx'S^\omega\cap M^\omega\subseteq xS^\omega\cap M^\omega. This union is disjoint because no two distinct elements of L⊥L_{\perp} are prefixes of one another; since the probability of each xSω∩MωxS^\omega\cap M^\omega is P(x)\mathbf{P}(x) we can indeed conclude that P(L)\mathbf{P}(L) is the probability that an infinite trajectory starting in aa first moves along a path in LL.

Remark 4.1. The reason for this generality of (11), as opposed to specifying P(L)\mathbf{P}(L) only relative to languages LL of the form L=s0L′L = s_0L' for the fixed initial state s0s_0 of the DTMC, is that we are analysing “sub-chains” and “sub-MRMs” within larger systems and need flexibility around starting states. This is completely analogous to how Ábrahám et al. [2] deal with probabilities of path sets represented by a set of finite prefixes.

Definition 4.2. For a DTMC M=(S,s0,P)M = (S, s_0, \mathbf{P}) and a set of states A⊆SA \subseteq S, let

inp⁡(M,A)={s∈S:s=s0∨P((S−A)s)>0}(12)\operatorname{inp}(M,A) = \{s \in S: s = s_0 \mathbin{\lor} \mathbf{P}((S-A)s) > 0\} \tag*{(12)}

denote the set of input states of AA.

In other words, inp⁡(M,A)\operatorname{inp}(M,A) is the set of states in AA that either coincide with the initial state of MM or are reachable from outside of AA in one step. For example, the input set of {(1,0),(1,1)}\{(1,0),(1,1)\} in the DTMC underlying the MRM in Figure 3 is simply {(1,0),(1,1)}\{(1,0),(1,1)\} again; had we chosen the set of all states except for (2,2)(2,2) and (2,∞)(2,\infty), then its input set would simply have been {(0,0)}\{(0,0)\}.

Before we define the path abstraction algorithm, we need a compact method, enabling a smooth mechanisation in Isabelle, to represent languages that are of the form L1L2…LnL_1L_2\ldots L_n where Li=aiA∗L_i = a_iA^* for some ai∈Aa_i \in A for every odd ii and Li=biL_i = b_i for some bi∉Ab_i \notin A for every even ii, or the other way around, where A⊆SA \subseteq S, that we need to express probability masses in, for the path abstraction algorithm.

Definition 4.3. Define red⁡:2S×S∗→S∗\operatorname{red} : 2^{S \times S^*} \to S^* by, for each A⊆SA \subseteq S, defining red⁡(A):S∗→S∗:x↦red⁡(A,x)\operatorname{red}(A) : S^* \to S^* : x \mapsto\operatorname{red}(A,x) inductively with two base cases. Thus, let A⊆SA \subseteq S. We set red⁡(A)(ϵ)=ϵ\operatorname{red}(A)(\epsilon) = \epsilon (for all a∈Sa \in S, or all a,b∈Sa,b \in S and x∈S∗x \in S^*, we set

red⁡(A)(abx)={red⁡(A)(ax),if a∈A∧b∈A,a(red⁡(A)(bx)),otherwise.(13)\operatorname{red}(A)(abx) = \begin{cases} \operatorname{red}(A)(ax), & \text{if } a \in A \mathbin{\land} b \in A,\\ a(\operatorname{red}(A)(bx)), & \text{otherwise.} \end{cases} \tag*{(13)}

The above recursive definition terminates, as the second argument decreases in length upon recursion. Intuitively, red⁡(A)\operatorname{red}(A) replaces, when applied to xx, all its maximal factors over AA by their respective first letters. The function red⁡\operatorname{red} comes in handy in representing languages of the form L1L2…LnL_{1}L_{2}\ldots L_{n} where Li=aiA∗L_{i}=a_{i}A^{*} for some ai∈Aa_{i}\in A for every odd ii and Li=biL_{i}=b_{i} for some bi∉Ab_{i}\notin A for every even ii, or the other way around, where A⊆SA\subseteq S: they are equal to, respectively,

(red⁡(A)−1(a1b2…(a∣b)n))⊥\left(\operatorname{red}(A)^{-1}(a_{1}b_{2}\ldots(a\mid b)_{n})\right)_{\perp}

and

(red⁡(A)−1(b1a2…(a∣b)n))⊥.\left(\operatorname{red}(A)^{-1}(b_{1}a_{2}\ldots(a\mid b)_{n})\right)_{\perp}.

Definition 4.4. Let M=(S,s0,P)M=(S,s_{0},\mathbf{P}) be a DTMC. For A⊆SA\subseteq S, set abstr⁡(A,M)≡(S,s0,P′)\operatorname{abstr}(A,M)\equiv(S,s_{0},\mathbf{P}') where P′:S+→[0,1]\mathbf{P}':S^{+}\to[0,1] is defined6 by P′(s)≡1\mathbf{P}'(s)\equiv1 for all s∈Ss\in S (interpreted as 1-letter words here), and, for all x∈S+x\in S^{+} with ∣x∣≥2\lvert x\rvert\ge2,

P′(x)={P(red⁡(A)−1(x)),if x∈(S−(A−inp⁡(M,A)))∗,0,otherwise.(14)\mathbf{P}'(x)= \begin{cases} \mathbf{P}\left(\operatorname{red}(A)^{-1}(x)\right), & \text{if }x\in\left(S-\left(A-\operatorname{inp}(M,A)\right)\right)^{*},\\ 0, & \text{otherwise.} \end{cases} \tag*{(14)}

In obtaining abstr⁡(A,M)\operatorname{abstr}(A,M) from MM, the set AA is called the abstraction set.

Path abstraction yields a DTMC again [10 Lemma 2]:

Theorem 4.1 (Abstr.thy/abstr_well_defined). If M=(S,s0,P)M=(S,s_{0},\mathbf{P}) is a DTMC in the free monoid view of Def. 3.1, so is abstr⁡(A,M)\operatorname{abstr}(A,M), for any A⊆SA\subseteq S.

To understand the new DTMC (S,s0,P′)(S,s_{0},\mathbf{P}'), we can examine the values P′\mathbf{P}' takes on two-state sequences, as they fully determine P′\mathbf{P}', because of Thm. 4.1. Thus let s,t∈Ss,t\in S. From Def. 4.3 we establish that

red⁡(A)−1(st)={∅,if s∈A∧t∈A,sA∗t,if s∈A∧t∉A,stA∗,if s∉A∧t∈A,st,if s∉A∧t∉A.(15)\operatorname{red}(A)^{-1}(st)= \begin{cases} \varnothing, & \text{if }s\in A\land t\in A,\\ sA^{*}t, & \text{if }s\in A\land t\notin A,\\ stA^{*}, & \text{if }s\notin A\land t\in A,\\ st, & \text{if }s\notin A\land t\notin A. \end{cases} \tag*{(15)}

and thus applying ⊥\perp to these languages gives ∅\varnothing, sA∗tsA^{*}t, stst, and stst, respectively. Taking into account Def. 4.1 and (14), and writing φ=s∈A−inp⁡(M,A)∨t∈A−inp⁡(M,A)\varphi=s\in A-\operatorname{inp}(M,A)\lor t\in A-\operatorname{inp}(M,A) for convenience, we thus obtain

P′(st)={0,if s∈A∧t∈A∨φ,P(sA∗t),if s∈A∧t∉A∧¬φ,P(st),otherwise.(16)\mathbf{P}'(st)= \begin{cases} 0, & \text{if }s\in A\land t\in A\lor\varphi,\\ \mathbf{P}(sA^{*}t), & \text{if }s\in A\land t\notin A\land\lnot\varphi,\\ \mathbf{P}(st), & \text{otherwise.} \end{cases} \tag*{(16)}

In other words, transitions (with positive probabilities) between states in AA are removed, and transitions from or to states in AA that are not part of the set inp⁡(M,A)\operatorname{inp}(M,A) of input states of AA are removed as well; transitions from outside of AA to inp⁡(M,A)\operatorname{inp}(M,A) are left unaltered, and transitions from inp⁡(M,A)\operatorname{inp}(M,A) to the outside of AA are replaced by the total probability of starting in a state in inp⁡(M,A)\operatorname{inp}(M,A), moving through AA, and then ending up in a state outside of AA reachable from AA in one step. Intuitively, we are modifying the sub-chain induced by AA, i.e. the chain with state space A∪{s∈S−A:P(As)>0}A \cup\{s \in S - A: \mathrm{P}(As) > 0\}, into a chain where we remove all of its transitions but introduce new transitions from inp⁡(M,A)\operatorname{inp}(M,A) to {s∈S−A:P(As)>0}\{s \in S - A: \mathrm{P}(As) > 0\} with probabilities equal to the respective reachability probabilities within that sub-chain.

Proving or mechanising Thm. 4.1 is more difficult than it would be in the classical view, but in return, theorems about applying path abstraction multiple times become easier to prove, such as monotonic absorption [10 Thm. 3]:

Theorem 4.2 (Abstr.thy/monotonic absorption). Let M=(S,s0,P)M = (S, s_0, \mathrm{P}) be a free-monoid DTMC as per Def. 3.1 and Conv. 2. If A⊆B⊆SA \subseteq B \subseteq S, then we have abstr⁡(B,abstr⁡(A,M))=abstr⁡(B,M)\operatorname{abstr}(B, \operatorname{abstr}(A,M)) = \operatorname{abstr}(B,M).

Remark 4.2. Since adding or removing isolated states (states that have zero incoming and zero outgoing probability) from an abstraction set has no effect on the abstraction, we may at each abstraction stage simply remove them or add them. This means in practice that (1) along a sequence of path abstractions, we can shrink the state space each time to the set of non-isolated states, reducing state space complexity along the way, and (2) as a consequence of (1), the SCC heuristic of [2] for choosing sequences of abstraction sets is sound, in the sense that it preserves total reachability probabilities and expected rewards to reach a set of goal states. Since defining and verifying correctness of a version of path abstraction that does incorporate shrinkage of state spaces in line with (1) adds little conceptual or proof engineering complexity, we instead focus on the pure monotonic absorption properties, Thm. 4.2 and Thm. 4.4, themselves, and on developing the machinery to verify these properties. Then, the machinery can straightforwardly be extended to match concrete heuristics.

Now, we extend Def. 4.4 to MRMs, aiming to preserve expected rewards.

Definition 4.5. Let M=(S,s0,P,R)M = (S, s_0, \mathrm{P}, R) be an MRM, with M=(S,s0,P)M = (S, s_0, \mathrm{P}). Let A⊆SA \subseteq S. Writing (S,s0,P′)=abstr⁡(A,M)(S, s_0, \mathrm{P}') = \operatorname{abstr}(A,M) as in Def. 4.4, set abstr⁡(A,M)≡(S,s0,P′,R′)\operatorname{abstr}(A,M) \equiv(S, s_0, \mathrm{P}', R') where R′:S+→RR' : S^{+} \to\mathbb{R} is defined by, for x∈S+x \in S^{+},

R′(x)≡{1P′(x)∑y∈(red⁡(A)−1(x))⊥P(y)R(y),if ∣x∣>1∧P′(x)>0,0,otherwise.(17)R'(x) \equiv \begin{cases} \frac{1}{\mathrm{P}'(x)} \sum_{y \in(\operatorname{red}(A)^{-1}(x))^\perp} \mathrm{P}(y)R(y), & \text{if } |x| > 1 \wedge\mathrm{P}'(x) > 0,\\ 0, & \text{otherwise.} \end{cases} \tag*{(17)}

Remark 4.3. Defining R′R' to map into R\mathbb{R} is only possible if the sum in the first case in (17) converges. We mechanise in Isabelle/HOL that this is indeed the case, which is Thm. 5.3, from which follows that expected rewards until hitting a goal set in terms of their defining sums converge. Our mechanisation of this convergence fact is, to the best of our knowledge, the first in an interactive theorem prover in terms of lightweight finite-prefix and real analysis semantics. Convergence of such expected rewards was established in Hölzl’s work [13], in the measure-theoretic semantics, using properties of random variables on probability spaces. This convergence fact is crucial in analysing what happens in the case of multiple path abstractions, most specifically the monotonic absorption property of path abstraction for MRMs.

Theorem 4.3 (Abstr.thy/MRM_abstr_well-defined). If M=(S,s0,P,R)\mathcal{M} = (S, s_0, \mathbf{P}, R) is an MRM in the free monoid view of Def. 3.1, then so is abstr⁡(A,M)\operatorname{abstr}(A,\mathcal{M}), for any A⊆SA \subseteq S.

Theorem 4.4 (Abstr.thy/MRM_monotonic_absorption). Let M=(S,s0,P,R)\mathcal{M} = (S, s_0, \mathbf{P}, R) be a free-monoid MRM as per Def. 3.1 and Conv. 2. If A⊆B⊆SA \subseteq B \subseteq S, we have abstr⁡(B,abstr⁡(A,M))=abstr⁡(B,M)\operatorname{abstr}(B,\operatorname{abstr}(A,\mathcal{M})) = \operatorname{abstr}(B,\mathcal{M}).

Path Abstraction as PMC

Now, we argue why a single application of path abstraction allows us to compute reachability probabilities and expected rewards as directly as one could wish, illustrated by a further refinement of the MRM in Figure 4 as an example. Then, we briefly show why path abstraction relative to abstraction sets that do not contain goal states preserves reachability probabilities and expected rewards, under the assumption that there is no interaction between the goal states—i.e. there are no transitions of positive probability between them, using the later result that path abstraction on MRMs satisfies a monotonic absorption property.

We take an MRM M=(S,s0,P,R)\mathcal{M} = (S, s_0, \mathbf{P}, R) and a set of goal states G⊆SG \subseteq S. We assume that the goal states do not interact; i.e. there do not exist states s,t∈Gs,t \in G with s≠ts \ne t for which P(st)>0\mathbf{P}(st) > 0. For example, we can assume that no goal state has outgoing probability, as in our example in Figure 2, or, as is often done in PMC if the modelled DTMC has to be strictly stochastic, that the goal states are absorbing: P(ss)=1\mathbf{P}(ss) = 1 for all s∈Gs \in G. In both cases, no goal state has outgoing probability to a non-goal state. We now examine what happens if we abstract M\mathcal{M} over the largest set that makes sense, i.e. the set of all non-goal states S−GS - G. In other words, we compute M′=(S,s0,P′,R′)\mathcal{M}' = (S, s_0, \mathbf{P}', R') where (S,s0,P′,R′)=abstr⁡(S−G,M)(S, s_0, \mathbf{P}', R') = \operatorname{abstr}(S - G,\mathcal{M}). We have inp⁡(M,S−G)={s0}\operatorname{inp}(\mathcal{M},S-G) = \{s_0\}, so the only transitions of positive probability in M′\mathcal{M}' are (at most the set) {(s0,g):g∈G}\{(s_0,g): g \in G\}, each one having, following (16), probability

P′(s0g)=P(s0(S−G)∗g)=∑x∈s0(S−G)∗gP(x),\mathbf{P}'(s_0g) = \mathbf{P}(s_0(S-G)^*g) = \sum_{x \in s_0(S-G)^*g} \mathbf{P}(x),

where the last equality follows from Def. 4.1 as

(s0(S−G)∗g)⊥=s0(S−G)∗g.(s_0(S-G)^*g)_{\perp} = s_0(S-G)^*g.

Summing over g∈Gg \in G then yields

P′(◊G)=∑g∈GP′(s0g)=∑x∈s0(S−G)∗GP(x)=P(◊G),(18)\mathbf{P}'(\lozenge G) = \sum_{g \in G} \mathbf{P}'(s_0g) = \sum_{x \in s_0(S-G)^*G} \mathbf{P}(x) = \mathbf{P}(\lozenge G), \tag*{(18)}

where the last equality follows from (8). In other words, the probabilities of the transitions in the abstracted MRM M′=abstr⁡(S−G,M)\mathcal{M}' = \operatorname{abstr}(S-G,\mathcal{M}) sum up to the exact reachability probability P(◊G)\mathbf{P}(\Diamond G) in the original MRM. The difference from M\mathcal{M} is that the total reachability probability to GG is now encoded in the most elementary way possible.

Since M′\mathcal{M}' is an easy-to-understand MRM, analogously to calculating the total reachability probability to reach GG there, we can calculate the total expected reward by multiplying probability by reward for each transition, and then summing those over g∈Gg \in G. Given g∈Gg \in G, we have

P′(s0g)R′(s0g)=∑x∈s0(S−G)∗gP(x)R(x)(19)\mathbf{P}'(s_0g)\mathbf{R}'(s_0g) = \sum_{x \in s_0(S-G)^{*}g} \mathbf{P}(x)\mathbf{R}(x) \tag*{(19)}

by (17) and the characterisation of the inverse image of red⁡(A)\operatorname{red}(A) on two-state sequences in (15). It follows that

E′(◊G)=∑g∈GP′(s0g)R′(s0g)=∑x∈s0(S−G)∗GP(x)R(x)=E(◊G),(20)\begin{aligned} \mathbf{E}'(\Diamond G) &= \sum_{g \in G} \mathbf{P}'(s_0g)\mathbf{R}'(s_0g) \\ &= \sum_{x \in s_0(S-G)^{*}G} \mathbf{P}(x)\mathbf{R}(x) = \mathbf{E}(\Diamond G), \tag*{(20)} \end{aligned}

where E′(◊G)\mathbf{E}'(\Diamond G) denotes the expected reward to reach GG in M′\mathcal{M}', and the final equality in the above follows from (8).

We have thus established that abstracting MRMs over the set of non-goal states preserves reachability probabilities and expected rewards. If we establish Thm. 4.3 and Thm. 4.4, then we have proven that an abstraction over any set of non-goal states preserves these quantities as well.

Example 4.1. One can further abstract the MRM in Figure 4 over the set of non-terminal states S−{(2,2),(2,∞)}S - \{(2,2),(2,\infty)\} to obtain the MRM in Figure 5, where we do not draw states that become isolated. We can read off that the probability P(◊{(2,2),(2,∞)})\mathbf{P}(\Diamond\{(2,2),(2,\infty)\}) of termination is 59+49=1\frac{5}{9}+\frac{4}{9}=1, thus the program terminates almost surely. Furthermore, the conditional expected time to reach the state corresponding to the division by zero given that we will end up in this state can be directly read off as E(◊(2,∞))=353\mathbf{E}(\Diamond(2,\infty))=\frac{35}{3}; the total expected time to reach termination is calculated as 59⋅15715+49⋅353=11\frac{5}{9}\cdot\frac{157}{15}+\frac{4}{9}\cdot\frac{35}{3}=11, which is indeed higher than the previously established bound in (10). Then, monotonic absorption as established in Thm. 4.4 enables us to conclude that the fully model checked MRM in Figure 5 could also have been obtained by abstracting the initial MRM in Figure 2 over the set of non-terminal states directly.

Figure 5. The MRM from Figure 4 fully model checked

Verified Path Abstraction

Our formalisation work is as follows. We

  1. (5.1) formalise DTMCs and MRMs (Def. 3.1, Conv. 2) and

  2. (5.2) the path abstraction algorithms (Defs. 4.4 and 4.5),

(5.3) mechanise the algorithms’ well-definedness (Thms. 4.1 and 4.3), and (5.4) mechanise the monotonic absorption property of these algorithms (Thms. 4.2 and 4.4).

We use Isabelle’s standard HOL-Library.Sublist to represent and reason with words, languages, and free monoids, and HOL-Analysis.Infinite_Sum to reason about infinite sums, which uses Def. 2.1 as the definition of infinite sums.

MRMs in Isabelle

Our formalisation design of Def. 3.1 and Conv. 2 in Isabelle/HOL is as follows. We define the type synonyms

’a lang=“’a list set”\text{’a lang} = \text{“’a list set”}
’a dtmc=“’a set×’a×(’a lang⇒real)”\text{’a dtmc} = \text{“’a set} \times\text{’a} \times\text{(’a lang} \Rightarrow\text{real)”}

and define our class of DTMCs DTMCDTMC :: “’a dtmc set”, through

definition DTMCDTMC :: “’a dtmc set” where

“DTMC≡{(S,s0,P).finite S∧s0∈S∧P∈problang}”“DTMC \equiv\{(S, s0, P). \text{finite } S \land s0 \in S \land P \in problang\}”

where problangproblang :: “’a lang ⇒\Rightarrow real” represents transition probability functions independent of state space through singleton languages, embedding the natural extension to languages of (11). Its definition involves several auxiliary functions; for clarity, we therefore prove a characterisation lemma for the class problangproblang:

lemma problang_charproblang\_char: “problang={P.(∃A.finite Aproblang = \{P. (\exists A. \text{finite } A

∧(∀xs. (xs∉lists A∧length xs≥2⟶P {xs}=0))\land(\forall xs.\ (xs \notin\text{lists } A \land\text{length } xs \ge2 \longrightarrow P\ \{xs\} = 0))
∧P {[]}=0∧(∀s. P {[s]}=1)∧(∀xs. P {xs}≥0)\land P\ \{\texttt{[]}\} = 0 \land(\forall s.\ P\ \{[s]\} = 1) \land(\forall xs.\ P\ \{xs\} \ge0)
∧(∀s. sum (λt. P {[s,t]}) {t. P {[s,t]}≠0}≤1)\land(\forall s.\ \text{sum}\ (\lambda t.\ P\ \{[s,t]\})\ \{t.\ P\ \{[s,t]\} \ne0\} \le1)
∧(∀xs s ys. P {xs@s#ys}=P {xs@[s]}∗P {s#ys})\land(\forall xs\ s\ ys.\ P\ \{xs @ s \mathbin{\#} ys\} = P\ \{xs @ [s]\} * P\ \{s \mathbin{\#} ys\})
∧(∀L. P L=infsum (λxs. P {xs}) (lminpfx L))}”(21)\land(\forall L.\ P\ L = \text{infsum}\ (\lambda xs.\ P\ \{xs\})\ (\text{lminpfx } L))\}” \tag*{(21)}

Here, lminpfxlminpfx :: “’a lang ⇒\Rightarrow ’a lang” is Isabelle’s counterpart of taking the prefix-minimal part L⊥L_{\perp} of a language LL:

definition lminpfxlminpfx :: “’a lang ⇒\Rightarrow ’a lang” where “lminpfx Llminpfx\ L

≡{xs∈L. ∀xs′∈L. prefix xs′ xs⟶xs′=xs}”\equiv\{xs \in L.\ \forall xs' \in L.\ \text{prefix } xs'\ xs \longrightarrow xs' = xs\}”

Remark 5.1. The most natural way to encode a probability function on the free monoid of a state space is to assign zero probability to paths of length ≥2\ge2 that contain states outside of the state space, to assign probability 1 to any path of length 1, and to assign probability 0 to the empty word. The problem with encoding an explicit state space is that each time we need to chain the condition that some probability function is inside a class for access to to-be-proven convergence lemmas, we need to supply the state space. To prevent these parametric conditions, we only encode that a finite state space confining the probability function to zero-ness on paths of length ≥2\ge2 that do not strictly run within the state space exists, cf. the first clause in the set comprehension of (21). This saves considerable boilerplate. The main results still apply in case one wants to restrict the probability function PP in a triple (S,s0,P)(S, s0, P) to be zero on lists of length ≥2\ge2 that are not in lists SS, as adding more conditions to a lemma breaks neither its proof nor its conclusion.

We now define MRM::“(′adtmc×(′alist⇒real))set”MRM :: “('a dtmc \times('a list \Rightarrow real)) set” as the class of MRMs, thus incorporating a reward function that acts on lists directly:

definition MRM:: “(′a dtmc×(′a list⇒real)) set”where “MRM={((S,s0,P),R).(S,s0,P)∈DTMC∧ (∀xs. length xs≤1∨P {xs}=0⟶R xs=0)∧ (∀xs a ys. P {xs@a#ys}≠0⟶R (xs@a#ys)=R (xs@[a])+R (a#ys))}”(22)\begin{aligned} \textbf{definition}\ MRM ::\ &“('a\ dtmc \times('a\ list \Rightarrow real))\ set” \\ \textbf{where}\ “MRM = \{((S, s0, P), R). &(S, s0, P) \in DTMC \\ &\land\ (\forall xs.\ length\ xs \le1 \lor P\ \{xs\} = 0 \longrightarrow R\ xs = 0) \\ &\land\ (\forall xs\ a\ ys.\ P\ \{xs @ a \# ys\} \ne0 \longrightarrow\\ &\qquad R\ (xs @ a \# ys) = R\ (xs @ [a]) + R\ (a \# ys))\}” \tag*{(22)} \end{aligned}

and thus directly specifying a reward function RR on paths, following Def. 3.1.

Formalising the Path Abstraction Algorithm

We have specified two path abstraction algorithms in Def. 4.4 and Def. 4.5, respectively, where the former can be immediately formulated in terms of the definition of MRMs (Def. 3.1), and the latter uses the former. We first formalise the algorithm for DTMCs:

definition abstr:: “′a set⇒′a dtmc⇒′a dtmc”where “abstr A M≡(fst M, fst (snd M),λL. (∑∞ xs∈lminpfx L. (if xs=[] then 0 else(if length xs=1 then 1 else(if (xs∈lists ((fst M)−(A−inp M A)))then (snd (snd (M)) (vimage (red A) {xs}) else 0))))”(23)\begin{aligned} \textbf{definition}\ abstr ::\ &“'a\ set \Rightarrow'a\ dtmc \Rightarrow'a\ dtmc” \\ \textbf{where}\ “abstr\ A\ M \equiv&(fst\ M,\ fst\ (snd\ M), \\ &\lambda L.\ (\sum_{\infty}\ xs \in lminpfx\ L.\ (\text{if } xs = []\ \textbf{then}\ 0\ \textbf{else} \\ &\qquad(\text{if } length\ xs = 1\ \textbf{then}\ 1\ \textbf{else} \\ &\qquad\quad(\text{if } (xs \in lists\ ((fst\ M) - (A - inp\ M\ A))) \\ &\qquad\qquad\textbf{then}\ (snd\ (snd\ (M))\ (vimage\ (red\ A)\ \{xs\})\ \textbf{else}\ 0))))” \tag*{(23)} \end{aligned}

We now specify inpinp and redred, Isabelle’s counterparts of Def. 4.2 and Def. 4.3. For inpinp, we have:

definition inp:: “′a dtmc⇒′a set⇒′a set” where“inp M A≡{t∈A. t=(fst (snd M))∨ (snd (snd M)) {[s,t]∣s. s∈(fst M)−A}≠0}”\begin{aligned} \textbf{definition}\ inp ::\ &“'a\ dtmc \Rightarrow'a\ set \Rightarrow'a\ set”\ \textbf{where} \\ &“inp\ M\ A \equiv\{t \in A.\ t = (fst\ (snd\ M)) \\ &\qquad\lor\ (snd\ (snd\ M))\ \{[s,t]\mid s.\ s \in(fst\ M) - A\} \ne0\}” \end{aligned}

The function red\mathit{red} is defined through an auxiliary function, so for understandability we specify it with a characterisation:

lemma red_char\mathit{red\_char}:

“red A []=[]\mathit{red}\ A\ [] = []” “red A [x]=[x]\mathit{red}\ A\ [x] = [x]”

“red A (x#y#xs)=(if (x∈A∧y∈A)\mathit{red}\ A\ (x \mathbin{\#} y \mathbin{\#} xs) = (\mathsf{if}\ (x \in A \mathbin{\land} y \in A) then red A (x#xs) else x# red A (y#xs))\mathsf{then}\ \mathit{red}\ A\ (x \mathbin{\#} xs)\ \mathsf{else}\ x \mathbin{\#}\ \mathit{red}\ A\ (y \mathbin{\#} xs))”

We are now ready to formalise the path abstraction algorithm for MRMs, as follows:

definition MRM_abstr\mathit{MRM\_abstr} :: “a set⇒(a dtmc×(a list⇒real))⇒(a dtmc×(a list⇒real))a\ \mathsf{set} \Rightarrow(a\ \mathsf{dtmc} \times(a\ \mathsf{list} \Rightarrow\mathsf{real})) \Rightarrow(a\ \mathsf{dtmc} \times(a\ \mathsf{list} \Rightarrow\mathsf{real}))” where

“MRM_abstr A MR≡case MR of (M,R)⇒\mathit{MRM\_abstr}\ A\ MR \equiv\mathsf{case}\ MR\ \mathsf{of}\ (M, R) \Rightarrow (let (S,s0,P)=M; (S,s0,Q)=abstr A M in(\mathsf{let}\ (S, s_0, P) = M;\ (S, s_0, Q) = \mathit{abstr}\ A\ M\ \mathsf{in} (abstr A M, λxs. (if (length xs>1∧Q {xs}≠0)(\mathit{abstr}\ A\ M,\ \lambda xs.\ (\mathsf{if}\ (\mathsf{length}\ xs > 1 \mathbin{\land} Q\ \{xs\} \ne0) then ((1/Q {xs})∗infsum (λys. P {ys}∗R ys)\mathsf{then}\ ((1 / Q\ \{xs\}) * \mathsf{infsum}\ (\lambda ys.\ P\ \{ys\} * R\ ys) (lminpfx (vimage (red A) {xs}))) else 0)))(\mathsf{lminpfx}\ (\mathsf{vimage}\ (\mathit{red}\ A)\ \{xs\})))\ \mathsf{else}\ 0)))”

Then, the underlying DTMC of an MRM gets mapped to its abstraction after applying abstr\mathit{abstr}; the new reward function is specified by mapping a path to the (conditional) expected reward on the abstract path defined by vimage (red A) {xs}\mathsf{vimage}\ (\mathit{red}\ A)\ \{xs\}, conforming to Def. 3.1.

Mechanising Well-Definedness

We now describe the mechanisation of the well-definedness properties of the path abstraction algorithms for DTMCs and MRMs, respectively, i.e. Thms. 4.1 and 4.3. Their Isabelle counterparts are, respectively, (25) and (26):

lemma abstr_well_defined\mathit{abstr\_well\_defined}:

assumes “M∈DTMCM \in\mathit{DTMC}” “A⊆fst MA \subseteq\mathsf{fst}\ M”

shows “abstr A M∈DTMC\mathit{abstr}\ A\ M \in\mathit{DTMC}”

lemma MRM_abstr_well_defined\mathit{MRM\_abstr\_well\_defined}:

assumes “(M,R)∈MRM(M, R) \in\mathit{MRM}” “M=(S,s0,P)M = (S, s_0, P)” “A⊆SA \subseteq S”

shows “MRM_abstr A (M,R)∈MRM\mathit{MRM\_abstr}\ A\ (M, R) \in\mathit{MRM}”

We now give the proof outlines of those, in the notation of their mathematical counterparts Thms. 4.1 and 4.3. In these outlines, we indicate where proof engineering complexity in Isabelle diverges from conceptual complexity to highlight the mechanisation contributions.

Proof outline of Thm. 4.1. We follow the pen-and-paper proof in [11 App. B]. Thus, let M=(S,s0,P)M = (S, s_0, \mathbf{P}) be a DTMC, where SS is a finite set, s0∈Ss_0 \in S, and P:U∗→R\mathbf{P}: \mathbf{U}^{*} \to\mathbb{R} is such that P\mathbf{P} is in the right-hand set of (21), where we fix U\mathbf{U} as the universal set of symbols. For simplicity, we omit the brackets for singleton languages. Spelled out, (1) there exists a finite set AA such that P(x)=0\mathbf{P}(x)=0 for all x∈U∗−A∗x \in\mathbf{U}^{*}-A^{*} with ∣x∣≥2\lvert x\rvert\ge2; (2) P(ϵ)=0\mathbf{P}(\epsilon)=0; (3) P(s)=1\mathbf{P}(s)=1 for all s∈Us \in\mathbf{U}; (4) P:U∗→[0,∞)\mathbf{P}:\mathbf{U}^{*}\to[0,\infty); (5) for all x,y∈Ux,y\in\mathbf{U} and s∈Us\in\mathbf{U} we have P(xsy)=P(xs)P(sy)\mathbf{P}(xsy)=\mathbf{P}(xs)\mathbf{P}(sy); and (7) for all L⊆U∗L\subseteq\mathbf{U}^{*} we have P(L)=∑x∈L⊥P(x)\mathbf{P}(L)=\sum_{x\in L_{\perp}}\mathbf{P}(x). Write M′=(S,s0,P′)M'=(S,s_{0},\mathbf{P}') for the abstracted DTMC M′=abstr⁡(A,M)M'=\operatorname{abstr}(A,M), where A⊆SA\subseteq S, with AA not to be confused with the AA from condition (1). We are thus done if we can establish that P′\mathbf{P}' satisfies conditions (1), …\ldots, (7) as well. Condition (1) is satisfied by P′\mathbf{P}' if we choose SS as our finite set, and then follows directly from (23). Conditions (2) and (3) for P′\mathbf{P}' also follow immediately from (23). Condition (4) follows directly from (4) for P\mathbf{P} and (23) combined. Condition (7) for P′\mathbf{P}' follows immediately from how (23) specifies how P′\mathbf{P}' behaves on languages. At this point, to prove that P′\mathbf{P}' satisfies conditions (5) and (6), conceptual complexity diverges from proof engineering complexity. Condition (5) is established for P′\mathbf{P}' as follows, in Abstr.thy/abstr_well_defined. Since P′\mathbf{P}' satisfies (1), ∑t∈U:P′(st)≠0P′(st)\sum_{t\in\mathbf{U}:\mathbf{P}'(st)\ne0}\mathbf{P}'(st) is a sum of finitely many numbers. For each such tt we have P′(st)≤P(red⁡(A)−1(st))\mathbf{P}'(st)\le\mathbf{P}(\operatorname{red}(A)^{-1}(st)) by (23), or, equivalently, by Def. 4.4. But the sum of the P(red⁡(A)−1(st))\mathbf{P}(\operatorname{red}(A)^{-1}(st))'s over these values of tt is P(L)\mathbf{P}(L) where L=⨆t∈U:P′(st)≠0(red⁡(A)−1(st))⊥L=\bigsqcup_{t\in\mathbf{U}:\mathbf{P}'(st)\ne0}(\operatorname{red}(A)^{-1}(st))_{\perp}, as L=L⊥L=L_{\perp}. We have L⊆sS+L\subseteq sS^{+} as its components are contained in sS+sS^{+} as well, and we may apply Thm. 5.1 to establish that P(L)≤1\mathbf{P}(L)\le1 and hence P′\mathbf{P}' satisfies condition (5). Condition (6) is then tackled as follows: if x,y∈U+x,y\in\mathbf{U}^{+} and s∈Us\in\mathbf{U} are such that xsy∈(S−(A−inp⁡(M,A)))∗xsy\in(S-(A-\operatorname{inp}(M,A)))^{*}, we have P′(z)=P(Lz)\mathbf{P}'(z)=\mathbf{P}(L_z) for each z∈{xs,sy,xsy}z\in\{xs,sy,xsy\} where Lz=(red⁡(A)−1(z))⊥L_z=(\operatorname{red}(A)^{-1}(z))_{\perp}.7 Then, proving P(Lxsy)=P(Lxs)⋅P(Lsy)\mathbf{P}(L_{xsy})=\mathbf{P}(L_{xs})\cdot\mathbf{P}(L_{sy}) comes down to proving

∑w∈LxsyP(w)=∑u∈LxsP(u)∑v∈LsyP(v)(24)\sum_{w\in L_{xsy}}\mathbf{P}(w)=\sum_{u\in L_{xs}}\mathbf{P}(u)\sum_{v\in L_{sy}}\mathbf{P}(v) \tag*{(24)}

which holds because Lxsy=⨆u∈Lxsu⋆LsyL_{xsy}=\bigsqcup_{u\in L_{xs}}u\star L_{sy}, most of whose foundation we mechanise in Freemonoid.thy/ltappend_lminpfx_vimage_red. Indeed: P\mathbf{P} converges on LxsyL_{xsy} because LxsyL_{xsy} is contained in a monoid on a finite set and all its words start with the first symbol of xsyxsy. We may thus use our variant of Tonelli’s theorem for non-negative real-valued functions—Thm. 5.2—applied to B=LxsyB=L_{xsy} and I=LxsI=L_{xs}—and the convergence result Thm. 5.1 for the languages LxsL_{xs}, LsyL_{sy}, and LxsyL_{xsy}, which is applicable because the three languages start with the first symbol of xsxs, sysy, and xsyxsy, respectively (note that these words are non-empty by assumption) and are contained in S+S^{+}. The edge cases x∉ϵ\y∉ϵ\xsy∉(S−(A−inp⁡(M,A)))∗x\notin\epsilon\backslash y\notin\epsilon\backslash xsy\notin(S-(A-\operatorname{inp}(M,A)))^{*} and x=ϵ∨y=ϵx=\epsilon\lor y=\epsilon are conceptually trivial and also do not pose further mechanisation challenges. □\square

Theorem 5.1 (Convergence Lemma I: Problang.thy/has_csp_finite-confinable-substoch). Given L⊆U+L\subseteq\mathbf{U}^{+} such that there exist a∈Ua\in\mathbf{U} and L′⊆U∗L'\subseteq\mathbf{U}^{*} and a finite A⊆UA\subseteq\mathbf{U} such that L=aL′L=aL' and L⊆A+L\subseteq A^{+}, a function P\mathbf{P} satisfying (1),…\ldots,(7) in the previous proof outline has the property that P(L)=∑x∈L⊥P(x)\mathbf{P}(L)=\sum_{x\in L_{\perp}}\mathbf{P}(x) converges to a real number in [0,1][0,1].

Proof. Conceptually, this follows by monotonicity of convergence of non-negative functions, combined with the observation that P(L)≤1P(L) \leq1 in case LL is finite, which follows by induction on the depth of L⊥L_{\perp}, i.e. the maximum length max⁡x∈L⊥∣x∣\max_{x \in L_{\perp}} |x| of a word in L⊥L_{\perp}. In Isabelle, one needs to work out these connections explicitly. We first establish, in Problang.thy/is_ltree_substoch, that P(L)≤1P(L) \leq1 with the additional assumption that LL is finite, by induction on the depth of L⊥L_{\perp}. The key idea is that chopping off the final symbols of the words in L⊥L_{\perp} of maximum length yields K⊥K_{\perp} of another language with depth one less than that of L⊥L_{\perp}; by grouping paths we thus establish P(L)≤P(K)P(L) \leq P(K), and we can reach all the way down to the base case P({a})=1P(\{a\}) = 1. Then, to prove that P(L)P(L) converges to a real number in [0,1][0,1], we use Isabelle’s nonneg_bdd_above_summable_on lemma to prove that P(L)P(L) converges at all, taking as preconditions that PP is a non-negative valued function and the set of its partial sums (w.r.t. finite subsets) is bounded from above by 1. Then, we use Isabelle’s infsum_nonneg_is_SUPREMUM_real lemma that states that a non-negative function converging on a set converges to the supremum of its partial sums; proving that the latter is in [0,1][0,1] is easy. □\quad\Box

Theorem 5.2 (Tonelli’s Theorem for non-negative functions: Problang.thy/double_sum). Let f:B→[0,∞)f : B \to[0,\infty) be a function from a set BB to the non-negative reals, such that ff converges on BB to a value y∈[0,∞)y \in[0,\infty):

∑x∈Bf(x)=y.\sum_{x \in B} f(x) = y.

Suppose that B=⨄i∈IBiB = \biguplus_{i \in I} B_i is a partition of BB, where II is an index set (possibly infinite). Then,

i↦∑x∈Bif(x) converges on I and ∑i∈I∑x∈Bif(x)=y.(25)i \mapsto\sum_{x \in B_i} f(x) \text{ converges on } I \text{ and } \sum_{i \in I} \sum_{x \in B_i} f(x) = y. \tag*{(25)}

Proof. This is Tonelli’s theorem for non-negative numbers. HOL-Analysis provides this result for sums over Σ\Sigma-types (has_sum_SigmaD), but our language decompositions are disjoint unions; rather than reindexing them as Σ\Sigma-types, we prove the union version directly from the bounded partial sums of non-negative functions. We first prove that ∑i∈J∑x∈Bif(x)≤y\sum_{i \in J} \sum_{x \in B_i} f(x) \leq y for every finite JJ, which is done via finite set induction on JJ; then, we use the same machinery from the nonneg_bdd_above_summable_on and infsum_nonneg_is_SUPREMUM_real lemmas to establish the first statement of (25) and with that its second. □\quad\Box

Proof outline of Thm. 4.3. Since, to the best of our knowledge, Thm. 4.3 is new in our semantic framework, we develop its proof and mechanisation from scratch. Thus, let M=(M,R)\mathcal{M} = (M, R) with M=(S,s0,P)M = (S, s_0, P). We extend the spirit of the proof outline of Thm. 4.1. Write M′=abstr⁡(A,M)\mathcal{M}' = \operatorname{abstr}(A, \mathcal{M}), M′=(S,s0,P′)\mathcal{M}' = (S, s_0, P'), and M′=(M′,R′)\mathcal{M}' = (M', R')—which is due to Def. 4.5. Due to Thm. 4.1 we already know that M′M' is a DTMC. We thus need to verify, conforming to (22), that (1) R′(x)=0R'(x) = 0 whenever x∈U∗x \in\mathbb{U}^{*} satisfies ∣x∣≤1|x| \leq1 or P′(x)=0P'(x) = 0, and (2) for all x,y∈U∗x,y \in\mathbb{U}^{*} and s∈Us \in\mathbb{U} for which P′(xsy)≠0P'(xsy) \ne0 we have R′(xsy)=R′(xs)+R′(sy)R'(xsy) = R'(xs) + R'(sy). The fact that condition (1) holds for R′R' is immediately due to (24). Condition (2) is established to hold for R′R' as follows. Write Lz=(red⁡(A)−1(z))⊥L_z = (\operatorname{red}(A)^{-1}(z))_{\perp} again, for z∈{xs,sy,xsy}z \in\{xs,sy,xsy\}. We first consider the case that xx and yy are non-empty and P′(xsy)≠0P'(xsy) \ne0 (which implies xsy∈(S−(A−inp⁡(M,A)))∗xsy \in(S - (A - \operatorname{inp}(M,A)))^{*}). Then, P′(xsy)R′(xsy)=P'(xsy)R'(xsy) = ∑w∈LxsyP(w)R(w)\sum_{w\in L_{xsy}} \mathbf{P}(w)R(w), P′(xsy)R′(xs)=∑v∈LsyP(v)∑u∈LxsP(u)R(u)\mathbf{P}'(xsy)R'(xs)=\sum_{v\in L_{sy}}\mathbf{P}(v)\sum_{u\in L_{xs}}\mathbf{P}(u)R(u), and ultimately P′(xsy)R′(sy)=∑u∈LxsP(u)∑v∈LsyP(v)R(v)\mathbf{P}'(xsy)R'(sy)=\sum_{u\in L_{xs}}\mathbf{P}(u)\sum_{v\in L_{sy}}\mathbf{P}(v)R(v), because we have P′(xsy)=P′(xs)P′(sy)\mathbf{P}'(xsy)=\mathbf{P}'(xs)\mathbf{P}'(sy) from Thm. 4.1. We thus wish to prove

∑w∈LxsyP(w)R(w)=∑v∈LsyP(v)∑u∈LxsP(u)R(u)+∑u∈LxsP(u)∑v∈LsyP(v)R(v).(26)\sum_{w\in L_{xsy}}\mathbf{P}(w)R(w)=\sum_{v\in L_{sy}}\mathbf{P}(v)\sum_{u\in L_{xs}}\mathbf{P}(u)R(u) +\sum_{u\in L_{xs}}\mathbf{P}(u)\sum_{v\in L_{sy}}\mathbf{P}(v)R(v). \tag*{(26)}

Using the property Lxsy=⋃˙u∈Lxsu⋆LsyL_{xsy}=\mathop{\mathbin{\dot{\bigcup}}}_{u\in L_{xs}}u\star L_{sy} we rewrite the first sum as

∑u∈Lxs∑v∈LsyP(u)P(v)(R(u)+R(v)),\sum_{u\in L_{xs}}\sum_{v\in L_{sy}}\mathbf{P}(u)\mathbf{P}(v)(R(u)+R(v)),

which is possible as Lxs⊆U∗sL_{xs}\subseteq\mathbb{U}^{*}s and Lsy⊆sU∗L_{sy}\subseteq s\mathbb{U}^{*}, which we also mechanise, so that we may apply P(u⋆v)=P(u)P(v)\mathbf{P}(u\star v)=\mathbf{P}(u)\mathbf{P}(v) and R(u⋆v)=R(u)+R(v)R(u\star v)=R(u)+R(v) because M=(S,s0,P,R)\mathcal{M}=(S,s_0,\mathbf{P},R) is an MRM. Redistributing terms gives (26). However, redistributing sums in interaction with Isabelle’s HOL-Analysis library is only allowed if we can prove that all summands converge, and all of a sudden Thm. 5.1 no longer suffices and we need to invent new machinery. The trick is to prove that, for a language LL of the form Lz=(red⁡(A)−1(z))⊥L_z=(\operatorname{red}(A)^{-1}(z))_{\perp} for z∈U∗z\in\mathbb{U}^{*}, the sum ∑w∈LzP(w)R(w)\sum_{w\in L_z}\mathbf{P}(w)R(w) converges in case RR is of the following special form: R(z)=∣z∣stR(z)=|z|_{st}, where s,t∈Ss,t\in S, which is the number of times stst appears as an edge in the path zz—cf. the formal definition of factor occurrence in § 2.1. Such sums are expected visiting times of the transition stst, whose convergence we prove in Thm. 5.3. It is not (too) hard to prove that for general RR we have the identity R(z)=∑s,t∈set⁡(z)∣z∣st⋅R(st)R(z)=\sum_{s,t\in\operatorname{set}(z)}|z|_{st}\cdot R(st), and we have expressed R(z)R(z) as a linear combination of the values of RR on the two-state factors of zz, which corresponds to computing a weighted sum of transition rewards w.r.t. how many times a transition occurs in a path. Given that, as w,u,vw,u,v range over their indexing sets in (26), we have set⁡(w),set⁡(u),set⁡(v)⊆S\operatorname{set}(w),\operatorname{set}(u),\operatorname{set}(v)\subseteq S, we may thus express each of R(w),R(u),R(v)R(w),R(u),R(v) as a linear combination of the values R(st)R(st) for s,t∈Ss,t\in S. Then, the convergence result Thm. 5.3 can be pushed to transform (26) for the special case RR is of the form R(z)=∣z∣stR(z)=|z|_{st} (where s,t∈Ss,t\in S) to the general case, and a smooth interaction with the HOL-Analysis library, in combination with the same instance of Tonelli’s theorem, Thm. 5.2, applied to B=LxsyB=L_{xsy} and I=LxsI=L_{xs}, follows. The remaining edge cases for xx and yy are easy, both conceptually and in proof engineering complexity. □\square

Theorem 5.3 (Convergence Lemma II: Problang.thy/evt_summable_vimage_red_all). Let x∈U∗x\in\mathbb{U}^{*}. Let P:U∗→R\mathbf{P}:\mathbb{U}^{*}\to\mathbb{R} satisfy the defining conditions of (21). Let A⊆UA\subseteq\mathbb{U} be a finite set of symbols. Write Lx=(red⁡(A)−1(x))⊥L_x=(\operatorname{red}(A)^{-1}(x))_{\perp}. Let a,b∈Ua,b\in\mathbb{U}. Then, the following sum converges:

∑y∈Lx∣y∣ab⋅P(y)(27)\sum_{y\in L_x}|y|_{ab}\cdot\mathbf{P}(y) \tag*{(27)}

Proof. Since the terms of (27) are non-negative, our goal comes down to giving a proper upper bound on the sum. Intuitively, as yy becomes larger, probabilities of

(added) transitions are multiplied while new occurrences of abab are only added, and we either “leak” probability constantly when looping through abab or the language is finite or the probabilities of paths are zero beyond visiting abab as a transition more than once. We proceed by a case distinction on xx. For ∣x∣≤1|x| \le1, LxL_x is finite and the sum in (27) trivially converges. For x=abyx = aby with a,b∈Ua,b \in U and y∈U∗y \in U^*, we proceed with reverse induction on yy. The case y=εy = \varepsilon comes down to proving that the sum of (27) converges for ∣x∣=2|x| = 2, which we prove in a separate lemma. Now, if (27) converges for some x=abyx = aby, let us prove that this is the case if we replace xx by abzcabzc where z∈U∗z \in U^* and c∈Uc \in U. Since ∣abz∣≥2|abz| \ge2, we can write abz=wdabz = wd where w∈U∗w \in U^* and d∈Ud \in U. Then, we have x=wdcx = wdc as our new xx. Since Lwdc=Lwd⋆LdcL_{wdc} = L_{wd} \star L_{dc} and Lwd⊆U∗dL_{wd} \subseteq U^*d and Ldc⊆dU∗L_{dc} \subseteq dU^* and (27) converges for x=wdx = wd by the induction hypothesis, we may use Thm. 5.4 applied to K=LwdK = L_{wd} and L=LdcL = L_{dc} and the fact that (27) converges for the two-letter word x=dcx = dc. This is mechanised in Problang.thy/evt_summable_vimage_red 2. The latter fact is seen as follows. Following the characterisation (15), LdcL_{dc} is infinite only if d∈A∧c∉Ad \in A \land c \notin A, in which case Ldc=dA∗cL_{dc} = dA^*c. If a∉A∨b∉Aa \notin A \lor b \notin A, then ∣y∣ab≤1|y|_{ab} \le1 for all y∈Ldcy \in L_{dc} and we have convergence. The interesting case is thus a∈A∧b∈Aa \in A \land b \in A. Defining U={v∈A:P(vA∗c)>0}U = \{v \in A : \mathbf{P}(vA^*c) > 0\}, which intuitively is the set of all states in AA such that cc is reachable from a path starting in vv moving through AA, with positive probability, we look at two cases. If a∉U∨b∉Ua \notin U \lor b \notin U, then one can show that for all y∈Ldcy \in L_{dc} with ∣y∣ab>0|y|_{ab} > 0 we have P(y)=0\mathbf{P}(y) = 0 and we have again convergence. For a∈U∧b∈Ua \in U \land b \in U, we have P(bA∗c)>0\mathbf{P}(bA^*c) > 0 by definition of UU and thus the set D={x∈bA∗c:P(x)>0}D = \{x \in bA^*c : \mathbf{P}(x) > 0\} is non-empty, as (bA∗c)⊥=bA∗c(bA^*c)_{\perp} = bA^*c, as c∉Ac \notin A. Let y−∈Dy_- \in D be of minimal length, and define the language

H={y:∃y′. y′∈Ldc∧y⊑y′}∩((bU∗∩U∗ab)−U∗abU+).H = \{y : \exists y'.\ y' \in L_{dc} \land y \sqsubseteq y'\} \cap((bU^* \cap U^*ab) - U^*abU^+).

Clearly, y−∉Hy_- \notin H because b≠cb \ne c. Now, H⊎{y−}H \uplus\{y_-\} is a language contained in the free monoid on a finite set and has a common starting point bb, so that we may use Thm. 5.1 to conclude that P(H⊎{y−})≤1\mathbf{P}(H \uplus\{y_-\}) \le1. Since (H⊎{y−})⊥=H⊎{y−}(H \uplus\{y_-\})_{\perp} = H \uplus\{y_-\} (because y−∈Dy_- \in D is of minimal length), we can use P(y−)>0\mathbf{P}(y_-) > 0 to deduce that 0≤p<10 \le p < 1 if we set p≡P(H)p \equiv\mathbf{P}(H). We now prove that P({y∈Ldc:∣y∣ab=n})≤pn−1\mathbf{P}(\{y \in L_{dc} : |y|_{ab} = n\}) \le p^{n-1} for n∈N+n \in\mathbb{N}^+, which comes with its own set of mechanisation challenges that we do not elaborate on here. It thus follows that, for x=dcx = dc, the sum in (27) can be bounded as

∑y∈Ldc∣y∣ab⋅P(y)≤∑n=1∞n⋅pn−1(28)\sum_{y \in L_{dc}} |y|_{ab} \cdot\mathbf{P}(y) \le\sum_{n=1}^{\infty} n \cdot p^{n-1} \tag*{(28)}

and this upper bound converges because 0≤p<10 \le p < 1, and does so to (1−p)−2(1-p)^{-2}, which is a standard result in undergraduate calculus and real analysis. □\square

Theorem 5.4 (Problang.thy/evt_summable_path_concatenation). Given K,L⊆U∗K,L \subseteq U^*, ∑x∈K⋆L∣x∣ab⋅P(x)\sum_{x \in K \star L} |x|_{ab} \cdot\mathbf{P}(x) converges if ∑x∈K∣x∣ab⋅P(x)\sum_{x \in K} |x|_{ab} \cdot\mathbf{P}(x) and ∑x∈L∣x∣ab⋅P(x)\sum_{x \in L} |x|_{ab} \cdot\mathbf{P}(x) do (to, say, L1L_1 and L2L_2, respectively), whenever K=K⊥K = K_{\perp} and L=L⊥L = L_{\perp} and there exist c,d∈Uc,d \in U such that K⊆cU∗∩U∗dK \subseteq cU^* \cap U^*d and L⊆dU∗L \subseteq dU^*.

Proof. The trick is to prove that for every finite F⊆K⋆LF \subseteq K \star L we have ∑x∈F∣x∣ab⋅P(x)≤L1+L2\sum_{x \in F} |x|_{ab} \cdot\mathbf{P}(x) \leq L_1 + L_2; applying the standard machinery from the nonneg_bdd_above_summable_on and infsum_nonneg_is_SUPREMUM_real lemmas again proves that ∑x∈K⋆L∣x∣ab⋅P(x)\sum_{x \in K \star L} |x|_{ab} \cdot\mathbf{P}(x) converges.

Mechanising Monotonic Absorption

We prove Thms. 4.2 and 4.4, the monotonic absorption properties. Their Isabelle counterparts are, respectively:

lemma monotonic_absorptionmonotonic\_absorption:

assumes “M∈DTMCM \in DTMC” “A⊆BA \subseteq B” “B⊆fst MB \subseteq fst\ M”

shows “abstr B (abstr A M)=abstr B Mabstr\ B\ (abstr\ A\ M) = abstr\ B\ M” (32)

lemma MRM_monotonic_absorptionMRM\_monotonic\_absorption:

assumes “(M,R)∈MRM(M, R) \in MRM” “M=(S,s0,P)M = (S, s_0, P)” “A⊆BA \subseteq B”

“B⊆SB \subseteq S” shows “MRM_abstr B (MRM_abstr A (M,R))MRM\_abstr\ B\ (MRM\_abstr\ A\ (M, R))

=MRM_abstr B (M,R)= MRM\_abstr\ B\ (M, R)” (33)

Proof outline of Thm. 4.2. We follow the pen-and-paper proof in [11 App. B]. Thus, let M=(S,s0,P)M = (S, s_0, \mathbf{P}) be a DTMC, and let A⊆B⊆SA \subseteq B \subseteq S. Write MA=(S,s0,PA)M_A = (S, s_0, \mathbf{P}_A), MB=(S,s0,PB)M_B = (S, s_0, \mathbf{P}_B), and MAB=(S,s0,PAB)M_{AB} = (S, s_0, \mathbf{P}_{AB}) for the abstractions MA=abstr(A,M)M_A = abstr(A, M), MB=abstr(B,M)M_B = abstr(B, M), and MAB=abstr(B,abstr(A,M))M_{AB} = abstr(B, abstr(A, M)), respectively. To prove MAB=MBM_{AB} = M_B, it thus suffices to prove PAB=PB\mathbf{P}_{AB} = \mathbf{P}_B. We fix an x∈U∗x \in\mathbb{U}^* and focus on the case ∣x∣≥2∧x∈(S−(B−inp(M,B)))∗|x| \geq2 \land x \in(S - (B - inp(M, B)))^* (the edge cases are easy to verify). Working out the summation details for PAB(x)\mathbf{P}_{AB}(x) and PB(x)\mathbf{P}_B(x), repeatedly applying the convergence lemma Thm. 5.1, gives

PAB(x)=∑y∈Lx:red(A,y)=y∑z∈KyP(z),(29)\mathbf{P}_{AB}(x) = \sum_{\substack{y \in L_x : red(A,y)=y}} \sum_{z \in K_y} \mathbf{P}(z), \tag*{(29)}
PB(x)=∑z∈LxP(z),(30)\mathbf{P}_B(x) = \sum_{z \in L_x} \mathbf{P}(z), \tag*{(30)}

where for w∈U∗w \in\mathbb{U}^* we write Kw≡(red(A)−1(w))⊥K_w \equiv(red(A)^{-1}(w))_\perp and Lw≡(red(B)−1(w))⊥L_w \equiv(red(B)^{-1}(w))_\perp. We prove

Lx=⨄y∈Lx:red(A,y)=yKy,L_x = \biguplus_{\substack{y \in L_x : red(A,y)=y}} K_y,

whose foundation we mechanise in Freemonoid.thy/lminpfx_monab. Then, we establish PAB(x)=PB(x)\mathbf{P}_{AB}(x) = \mathbf{P}_B(x) from (29) and (30), after applying Thm. 5.2 again, this time for B=LxB = L_x and I={y∈Lx:red(A,y)=y}I = \{ y \in L_x : red(A,y) = y \}.

Proof outline of Thm. 4.4. Take the notation for MAM_A, MBM_B, and MABM_{AB} in the previous proof outline—that of Thm. 4.2, and write M=(M,R)\mathcal{M} = (M, R), MA=(MA,RA)\mathcal{M}_A = (M_A, R_A), MB=(MB,RB)\mathcal{M}_B = (M_B, R_B), and MAB=(MAB,RAB)\mathcal{M}_{AB} = (M_{AB}, R_{AB}) for MRMs such that MA=abstr(A,M)\mathcal{M}_A = abstr(A, \mathcal{M}), MB=abstr(B,M)\mathcal{M}_B = abstr(B, \mathcal{M}), and MAB=abstr(B,abstr(A,M))\mathcal{M}_{AB} = abstr(B, abstr(A, \mathcal{M})). By Thm. 4.2, we already have MAB=MBM_{AB}=M_B. We are thus left with establishing that RAB=RBR_{AB}=R_B. Analogously to (the proof of) Thm. 4.2, working out sums for PAB(x)RAB(x)\mathbf{P}_{AB}(x)R_{AB}(x) and PB(x)RB(x)\mathbf{P}_B(x)R_B(x) (for the substantial, non-edge case for xx) gets us to a to-be-proven equality relating a double sum, coming from the side of PAB(x)RAB(x)\mathbf{P}_{AB}(x)R_{AB}(x), to a single sum, coming from the side of PB(x)RB(x)\mathbf{P}_B(x)R_B(x), which again is resolved by the identity Lx=⨄y∈Lx: red⁡(A,y)=yKyL_x = \mathbin{\mathop{\biguplus}_{y\in L_x:\,\operatorname{red}(A,y)=y}} K_y, which we have formalised in Freemonoid.thy/lminpfx_monab. Analogously to (the proof of) Thm. 4.3, we need to express reward functions on paths as linear combinations over transition rewards, and (repeatedly) apply Thm. 5.3 for the HOL-Analysis library to allow us to perform the necessary sum manipulations. □\square

Conclusion

We have extended model checking and counterexample refinement by path abstraction to MRMs and expected rewards, and lifted it onto a machine-checked foundation. In Isabelle/HOL, we formalised DTMCs and MRMs in the free monoid view, defined the two path abstraction algorithms, and mechanised their well-definedness and monotonic absorption. For DTMCs, we mechanised the pen-and-paper proofs of [11]; for MRMs, both the algorithm and its proofs are new. Since abstracting over all non-goal states is equivalent to PMC, monotonic absorption implies that path abstraction preserves reachability probabilities and expected rewards for any abstraction set sequence leading to S−GS-G.

Our work focuses on the correctness of algorithms rather than on contributing general results to Isabelle’s mathematical libraries. The lightweight finite-prefix semantics of the free monoid view allowed us to work with the infinite sums of HOL-Analysis instead of measure theory. We expect our convergence lemmas for probability masses and expected visiting times, and our language decomposition lemmas, to be reusable beyond path abstraction. We hope that the advantages of the free monoid view will lead to its more widespread use in formalisations of Markov models and PMC; and, more generally, that our work motivates carefully choosing the right representation for the ITP problem at hand, even if that representation turns out to be non-standard.

Our choice for Isabelle was partly motivated by our plan to use the Isabelle Refinement Framework [15, 16] to refine our formalised algorithms into efficient correct-by-construction implementations for use in a probabilistic model checker. This was recently done for interval iteration [14], a standard PMC algorithm that is however monolithic and does not provide explainable counterexamples. We expect the free monoid view to simplify this process compared to building on the classical view and its existing formalisations: it is inherently closer to the data structures needed to represent MRMs, and to the linear algebra operations that implement the algorithms’ abstract steps. Beyond this, we plan to mechanise the correspondence between the classical and the free monoid views (Thm. 3.1), and to extend our approach to further PCTL properties, starting with bounded reachability.

Calculation of Quantities in Example MRMs

We first show, by hand, how one obtains the MRM in Figure 4 from the MRM in Figure 2 when abstracting over the set A={(1,0),(1,1)}A = \{(1,0),(1,1)\}. Let us call the respective MRMs M\mathcal{M} and M′\mathcal{M}'. Both states in AA are reachable from the outside in one step, thus inp⁡(M,A)=A\operatorname{inp}(\mathcal{M}, A) = A. It follows that, in obtaining M′\mathcal{M}' from M\mathcal{M}, only the transitions between states in AA are removed, and new transitions from inp⁡(M,A)\operatorname{inp}(\mathcal{M}, A) to the set of states outside of AA reachable from AA in one step—namely, {(2,0),(2,1)}\{(2,0),(2,1)\}—are introduced, which, according to the characterisation in (16), get probabilities equal to the probabilities of the sets

{(1,0)((1,1)(1,0))∗(2,0),for ((1,0),(2,0)),((1,0)(1,1))+(2,1),for ((1,0),(2,1)),((1,1)(1,0))+(2,0),for ((1,1),(2,0)),(1,1)((1,0)(1,1))∗(2,1),for ((1,1),(2,1)).(31)\begin{cases} (1,0)((1,1)(1,0))^{*}(2,0), & \text{for } ((1,0),(2,0)),\\ ((1,0)(1,1))^{+}(2,1), & \text{for } ((1,0),(2,1)),\\ ((1,1)(1,0))^{+}(2,0), & \text{for } ((1,1),(2,0)),\\ (1,1)((1,0)(1,1))^{*}(2,1), & \text{for } ((1,1),(2,1)). \tag*{(31)} \end{cases}

with respect to the transition probability function of the old MRM M\mathcal{M}, which evaluate to

{(1+14+⋯ )⋅12=23,for ((1,0),(2,0)),12⋅(1+14+⋯ )⋅12=13,for ((1,0),(2,1)),12⋅(1+14+⋯ )⋅12=13,for ((1,1),(2,0)),(1+14+⋯ )⋅12=23,for ((1,1),(2,1)).(32)\begin{cases} \left(1+\frac{1}{4}+\cdots\right)\cdot\frac{1}{2}=\frac{2}{3}, & \text{for } ((1,0),(2,0)),\\ \frac{1}{2}\cdot\left(1+\frac{1}{4}+\cdots\right)\cdot\frac{1}{2}=\frac{1}{3}, & \text{for } ((1,0),(2,1)),\\ \frac{1}{2}\cdot\left(1+\frac{1}{4}+\cdots\right)\cdot\frac{1}{2}=\frac{1}{3}, & \text{for } ((1,1),(2,0)),\\ \left(1+\frac{1}{4}+\cdots\right)\cdot\frac{1}{2}=\frac{2}{3}, & \text{for } ((1,1),(2,1)). \tag*{(32)} \end{cases}

where we have used the well-known identity for the geometric series ∑n=0∞rn=11−r\sum_{n=0}^{\infty} r^n = \frac{1}{1-r} for −1<r<1-1 < r < 1, applied to r=14r = \frac{1}{4}.

Now, for the rewards for those newly introduced transitions, let us consider the path set (1,0)((1,1)(1,0))∗(2,0)(1,0)((1,1)(1,0))^{*}(2,0) in M\mathcal{M} for the transition ((1,0),(2,0))((1,0),(2,0)) in MRM M′\mathcal{M}'. The paths (1,0)(2,0)(1,0)(2,0), (1,0)(1,1)(1,0)(2,0)(1,0)(1,1)(1,0)(2,0), etc. have probabilities and rewards

12⋅118⋅5132⋅9⋯(33)\frac{1}{2}\cdot1\quad\frac{1}{8}\cdot5\quad\frac{1}{32}\cdot9\quad\cdots \tag*{(33)}

so that the reward for this transition in M′\mathcal{M}' times its probability 23\frac{2}{3} becomes

12⋅1+18⋅5+132⋅9+⋯=12(∑n=0∞(14)n+4⋅∑n=0∞n⋅(14)n)=12(43+169)=149\begin{aligned} \frac{1}{2}\cdot1+\frac{1}{8}\cdot5+\frac{1}{32}\cdot9+\cdots\\ &=\frac{1}{2}\left(\sum_{n=0}^{\infty}\left(\frac{1}{4}\right)^n+4\cdot\sum_{n=0}^{\infty}n\cdot\left(\frac{1}{4}\right)^n\right) \\ &=\frac{1}{2}\left(\frac{4}{3}+\frac{16}{9}\right) \\ &=\frac{14}{9} \end{aligned}

so that its reward becomes 149/23=73\frac{14}{9}/\frac{2}{3}=\frac{7}{3}, where we have used the standard identity ∑n=0∞n⋅rn=r(1−r)2\sum_{n=0}^{\infty} n\cdot r^n=\frac{r}{(1-r)^2} for −1<r<1-1 < r < 1, applied to r=14r = \frac{1}{4}. The rewards of the other transitions can be calculated analogously.

To obtain the MRM of Figure 5 from that of Figure 4, we first abstract over {(0,0),(0,1)}\{(0,0),(0,1)\}—which is similar to the previous abstraction, exploiting the closed forms for ∑n=0∞rn\sum_{n=0}^{\infty} r^n and ∑n=1∞n⋅rn\sum_{n=1}^{\infty} n \cdot r^n—and then over the full set of non-terminal states S−{(2,2),(2,∞)}S-\{(2,2),(2,\infty)\}. The fact that this gives the fully abstracted or model checked MRM—i.e. that of abstracting the MRM in Figure 2 immediately over its set of non-terminal states—follows from applying the monotonic absorption property (Thm. 4.4) twice, for the sequence of state sets

A1={(1,0),(1,1)},A_1 = \{(1,0),(1,1)\},
A2={(0,0),(0,1)},A_2 = \{(0,0),(0,1)\},
A3={(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)}.A_3 = \{(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)\}.

Indeed: since A2⊆A3A_2 \subseteq A_3 we have

abstr⁡(A3,abstr⁡(A2,abstr⁡(A1,M)))=abstr⁡(A3,abstr⁡(A1,M)).\operatorname{abstr}(A_3,\operatorname{abstr}(A_2,\operatorname{abstr}(A_1,\mathcal{M}))) = \operatorname{abstr}(A_3,\operatorname{abstr}(A_1,\mathcal{M})).

Since A1⊆A3A_1 \subseteq A_3 as well, the latter is equal to abstr⁡(A3,M)\operatorname{abstr}(A_3,\mathcal{M}), and the “biggest” set A3A_3 absorbs all other state sets.

References

  1. [1]Ábrahám, E., Jansen, N., Jantsch, S.: Probabilistic counterexamples through the ages. In: Bertrand, N., Dubslaff, C., Klüppelholz, S. (eds.) Principles of Formal Quantitative Analysis. LNCS, vol. 15760, pp. 174–196. Springer (2025). https://doi.org/10.1007/978-3-031-97439-7_8
  2. [2]Ábrahám, E., Jansen, N., Wimmer, R., Katoen, J.P., Becker, B.: DTMC model checking by SCC reduction. In: QEST. pp. 37–46. IEEE Computer Society (2010). https://doi.org/10.1109/QEST.2010.13
  3. [3]Agha, G., Palmskog, K.: A survey of statistical model checking. ACM Trans. Model. Comput. Simul. 28(1), 6:1–6:39 (2018). https://doi.org/10.1145/3158668
  4. [4]Baier, C., de Alfaro, L., Forejt, V., Kwiatkowska, M.: Model checking probabilistic systems. In: Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R. (eds.) Handbook of Model Checking, pp. 963–999. Springer (2018). https://doi.org/10.1007/978-3-319-10575-8_28
  5. [5]Baier, C., Haverkort, B.R., Hermanns, H., Katoen, J.P.: Performance evaluation and model checking join forces. Commun. ACM 53(9), 76–85 (2010). https://doi.org/10.1145/1810891.1810912
  6. [6]Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press (2008)
  7. [7]Budde, C.E., Hartmanns, A., Klauck, M., Kretínský, J., Parker, D., Quatmann, T., Turrini, A., Zhang, Z.: On correctness, precision, and performance in quantitative verification – QComp 2020 competition report. In: Margaria, T., Steffen, B. (eds.) ISoLA. LNCS, vol. 12479, pp. 216–241. Springer (2020). https://doi.org/10.1007/978-3-030-83723-5_15
  8. [8]Gordon, A.D., Henzinger, T.A., Nori, A.V., Rajamani, S.K.: Probabilistic programming. In: Herbsleb, J.D., Dwyer, M.B. (eds.) FOSE. pp. 167–181. ACM (2014). https://doi.org/10.1145/2593882.2593900
  9. [9]Hansson, H., Jonsson, B.: A logic for reasoning about time and reliability. Form. Asp. Comput. 6(5), 512–535 (1994). https://doi.org/10.1007/BF01211866
  10. [10]Hartmanns, A., Modderman, R.: DTMC model checking by path abstraction revisited. In: Ganty, P., Mansutti, A. (eds.) RP. LNCS, vol. 16230, pp. 186–201. Springer (2025). https://doi.org/10.1007/978-3-032-09524-4_13
  11. [11]Hartmanns, A., Modderman, R.: DTMC model checking by path abstraction revisited (extended version). CoRR abs/2509.02393 (2025). https://doi.org/10.48550/arXiv.2509.02393
  12. [12]Hölzl, J.: Markov chains and Markov decision processes in Isabelle/HOL. J. Autom. Reason. 59(3), 345–387 (2017). https://doi.org/10.1007/S10817-016-9401-5
  13. [13]Hölzl, J.: Markov processes in Isabelle/HOL. In: Bertot, Y., Vafeiadis, V. (eds.) CPP. pp. 100–111. ACM (2017). https://doi.org/10.1145/3018610
  14. [14]Kohlen, B., Schäfeler, M., Abdulaziz, M., Hartmanns, A., Lammich, P.: A formally verified IEEE 754 floating-point implementation of interval iteration for MDPs. In: Piskac, R., Takamaric, Z. (eds.) CAV. LNCS, vol. 15932, pp. 122–146. Springer (2025). https://doi.org/10.1007/978-3-031-98679-6_6
  15. [15]Lammich, P.: Automatic data refinement. In: Blazy, S., Paulin-Mohring, C., Pichardie, D. (eds.) ITP. LNCS, vol. 7998, pp. 84–99. Springer (2013). https://doi.org/10.1007/978-3-642-39634-2_9
  16. [16]Lammich, P., Tuerk, T.: Applying data refinement for monadic programs to Hopcroft’s algorithm. In: Beringer, L., Felty, A.P. (eds.) ITP. LNCS, vol. 7406, pp. 166–182. Springer (2012). https://doi.org/10.1007/978-3-642-32347-8_12
  17. [17]Royden, H.L., Fitzpatrick, P.: Real Analysis. Pearson modern classic, Pearson, New York, NY, 4th edn. (2018)
  18. [18]Schäffeler, M., Abdulaziz, M.: Formally verified solution methods for Markov decision processes. In: Williams, B., Chen, Y., Neville, J. (eds.) AAAI. pp. 15073–15081. AAAI Press (2023). https://doi.org/10.1609/AAAI.V37I12.26759

Paper details

vlnc:W_kygnrpa8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents