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 —a PCTL [9] formula asking whether the probability to reach a certain subset of goal states is at most some threshold —or to find a lower bound on , the expected reward (e.g. runtime cost) accumulated before reaching . 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 or expected reward queries for .
A DTMC is a stochastic process over a discrete state space and (time) index set 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 of moving from state to 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 does not hold, then a counterexample could be a set of paths, each of which reaches from the initial state, and which in total has a probability mass greater than . 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 not holding, the set of all paths that reach 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 , the set of non-goal states. Notably, performing path abstraction over 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 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 and then over a set of states yields the same result as abstracting over 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 , they use one of the form where is the free monoid on (i.e. the set of words over alphabet ), enabling smoother correctness proofs (notably for monotonic absorption). However, the proofs of [10] still fill 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 -algebra and circumventing having to reason about -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 denote the set of natural numbers, and the set of positive integers. For a set , we let denote its power set. Given a function and a set , we denote by the pre-image of under . The universal set is denoted by and is the equivalent of Isabelle’s UNIV.
Languages and the Free Monoid
Given a set , we let denote the set of all words that have letters in alphabet , and let denote the empty word. is called the free monoid on , and is indeed a monoid with the empty word as neutral element and concatenation of words as (an associative) binary operation on . Let denote the Kleene plus of : . The concatenation of two words and is denoted by . Given a word , we let denote the smallest subset of containing the letters of , i.e. . Note that is finite. Given we say that is a prefix of , denoted by , if there exists a word such that . Then, becomes a partial order on , called the prefix order. We say that is a factor of , denoted by , if there exist words such that ; we let denote the number of factor occurrences of in $x. For , we let denote the length of . Note that .
Let denote the set of all infinite sequences over . Note that one can concatenate a word over with an infinite sequence over , and that a word over can be a prefix of an infinite sequence over .
A set is called a language over the alphabet if , and we let denote the prefix-minimal part of . Note that .
The concatenation of two languages is denoted by and is defined by . Furthermore, the prefix order on extends to languages : we write if . Note that is a pre-order on but not a partial order (any two distinct languages containing precede each other w.r.t. ).
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 we let denote the tail of , where if and if for some and . The -operator extends to languages through (where ), and can hence also be used as the binary operation on where .
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 and . Then has infinite sum on , denoted , if
That is, if relative to every positive error tolerance there exists a finite subset of such that we can approximate by summing over any finite subset of containing .2 Eq. (1) is trivially satisfied if itself is finite.
Markov Chains and Reward Models
Definition 2.2. A (transition-based) Markov reward model () is a tuple with finite state space , initial state , transition probability function with , and reward function s.t. .
Definition 2.3. A discrete-time Markov chain () is a triple such that are the first three entries of an .
Given an , we call its underlying or induced . A further induces a directed graph with edge set , called the underlying graph of , which can also be seen as the underlying graph of .
To a we can associate the sets and 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 standard in the literature:
Theorem 2.1. Let be the -algebra on generated3 by the set . Then, there exists a unique function satisfying, for all ,
such that is a probability space, where is short for
in the first case of (2).
Proof. Argued in (the context of) [6 Def. 10.10].
Definition 2.4. Given a set of goal states, the unbounded reachability probability of reaching in is
Convention 1. We assume throughout that any set of goal states does not contain the initial state. We do this because in the case we trivially have , and there would be nothing substantial left to compute or to reason with.
Remark 2.1. Note that is the set of all paths in that contain a state in , and that
is a disjoint4 countable union of sets that are measurable by definition of in Thm. 2.1 and hence is itself measurable. As such, (3) is well-defined.
Definition 2.5. Let be an MRM. Then, given a set of goal states, the expected reward of reaching in is defined by
where is the expected value of the random variable defined by, where we write ,
Remark 2.2. Note that in (6) exists as an element of and is unique if , 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 . Note furthermore that in Def. 2.5 is indeed a random variable, as the image of under is countable and the inverse image of every real number under is a countable union of the basis sets (where ) of the -algebra from Thm. 2.1, together with possibly , whose measurability is seen through
which is a countable intersection of countable unions of basis sets of the -algebra 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 -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 in (3) and 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 , we have
where is short for for and , as written earlier in Thm. 2.1, and, analogously, is short for .
Proof of Thm. 3.1. For , we use (3) and (4) and the countable additivity rule of measures to deduce that . Note that for each by (2), and hence . Since if does not start in , we can replace the domain by . Since by Conv. 1, we have . Then, we obtain , and, given that for all by definition of , , and we have verified the first line of (8).
For , starting from (6), we note that the random variable encoding on finite paths is constant on each basis set () of the -algebra of the probability space on (it is constant with value 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.
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 and as abbreviations of the probability and (cumulative) reward of a path . 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 where is a finite set called the state space of ; is the initial state of ; is a function satisfying, for all , and and ; and is a function satisfying whenever and, for all and for which , .
The above definition captures the fact that the function 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 for all and , the function is fully determined by its values on two-state sequences. A similar argument applies to the reward function.
Convention 2. Within PMC, the condition for all in Def. 3.1 is often too strict and hence relaxed to for all . From now on, we adopt this convention.
In the free monoid view of MRMs, and 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.

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 of variables can take, where an undefined division is indicated with a -sign:
Here, the initial state is . Additionally, we would like to capture the (expected) time it takes to reach a terminal state. Suppose that a -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.

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 . 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 , with state space together with the states outside of that can be reached from within one step as terminal states. Figure 3 shows in grey and the sub-MRM within dotted lines.

Figure 3. The MRM of Figure 1 with sub-MRM induced by
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 from which one can reach an outside state (in this case all of ) to those outside states. The result is shown in Figure 4.

Figure 4. The MRM abstracted over into a new MRM
Here, the abstract path has probability , which is greater than 15%. Since path abstraction preserves5 reachability probabilities, we have where and are the transition probability functions of the MRMs of Figure 2 and Figure 4, respectively. Clearly, contributes to the sum constituting —see Thm. 3.1—and thus , and we do not run our program. Note that 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 to is .
We can also obtain information about other quantities of interest. For example, summing probability times reward over the two paths and in Figure 4 yields
which serves as a lower bound of .
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 in the free monoid view, as defined in Def. 3.1, with the relaxed substochasticity convention Conv. 2.
Definition 4.1. Given , let denote the infinite sum
where we recall that is the set of minimal elements of with respect to the prefix order .
In (11) we mostly focus on those of the form with and . Then, the interpretation of is that it is the probability that an infinite trajectory starting in state initially moves along a path in . Indeed: this probability is equal to the measure of the union of all basis sets where ranges over (where the -algebra involved is taken w.r.t. initial state ), which can be written as the disjoint union of all where ranges over the prefix-minimal part of —i.e. all minimal elements of w.r.t. the prefix order—because always implies . This union is disjoint because no two distinct elements of are prefixes of one another; since the probability of each is we can indeed conclude that is the probability that an infinite trajectory starting in first moves along a path in .
Remark 4.1. The reason for this generality of (11), as opposed to specifying only relative to languages of the form for the fixed initial state 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 and a set of states , let
denote the set of input states of .
In other words, is the set of states in that either coincide with the initial state of or are reachable from outside of in one step. For example, the input set of in the DTMC underlying the MRM in Figure 3 is simply again; had we chosen the set of all states except for and , then its input set would simply have been .
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 where for some for every odd and for some for every even , or the other way around, where , that we need to express probability masses in, for the path abstraction algorithm.
Definition 4.3. Define by, for each , defining inductively with two base cases. Thus, let . We set (for all , or all and , we set
The above recursive definition terminates, as the second argument decreases in length upon recursion. Intuitively, replaces, when applied to , all its maximal factors over by their respective first letters. The function comes in handy in representing languages of the form where for some for every odd and for some for every even , or the other way around, where : they are equal to, respectively,
and
Definition 4.4. Let be a DTMC. For , set where is defined6 by for all (interpreted as 1-letter words here), and, for all with ,
In obtaining from , the set is called the abstraction set.
Path abstraction yields a DTMC again [10 Lemma 2]:
Theorem 4.1 (Abstr.thy/abstr_well_defined). If is a DTMC in the free monoid view of Def. 3.1, so is , for any .
To understand the new DTMC , we can examine the values takes on two-state sequences, as they fully determine , because of Thm. 4.1. Thus let . From Def. 4.3 we establish that
and thus applying to these languages gives , , , and , respectively. Taking into account Def. 4.1 and (14), and writing for convenience, we thus obtain
In other words, transitions (with positive probabilities) between states in are removed, and transitions from or to states in that are not part of the set of input states of are removed as well; transitions from outside of to are left unaltered, and transitions from to the outside of are replaced by the total probability of starting in a state in , moving through , and then ending up in a state outside of reachable from in one step. Intuitively, we are modifying the sub-chain induced by , i.e. the chain with state space , into a chain where we remove all of its transitions but introduce new transitions from to 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 be a free-monoid DTMC as per Def. 3.1 and Conv. 2. If , then we have .
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 be an MRM, with . Let . Writing as in Def. 4.4, set where is defined by, for ,
Remark 4.3. Defining to map into 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 is an MRM in the free monoid view of Def. 3.1, then so is , for any .
Theorem 4.4 (Abstr.thy/MRM_monotonic_absorption). Let be a free-monoid MRM as per Def. 3.1 and Conv. 2. If , we have .
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 and a set of goal states . We assume that the goal states do not interact; i.e. there do not exist states with for which . 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: for all . In both cases, no goal state has outgoing probability to a non-goal state. We now examine what happens if we abstract over the largest set that makes sense, i.e. the set of all non-goal states . In other words, we compute where . We have , so the only transitions of positive probability in are (at most the set) , each one having, following (16), probability
where the last equality follows from Def. 4.1 as
Summing over then yields
where the last equality follows from (8). In other words, the probabilities of the transitions in the abstracted MRM sum up to the exact reachability probability in the original MRM. The difference from is that the total reachability probability to is now encoded in the most elementary way possible.
Since is an easy-to-understand MRM, analogously to calculating the total reachability probability to reach there, we can calculate the total expected reward by multiplying probability by reward for each transition, and then summing those over . Given , we have
by (17) and the characterisation of the inverse image of on two-state sequences in (15). It follows that
where denotes the expected reward to reach in , 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 to obtain the MRM in Figure 5, where we do not draw states that become isolated. We can read off that the probability of termination is , 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 ; the total expected time to reach termination is calculated as , 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
(5.1) formalise DTMCs and MRMs (Def. 3.1, Conv. 2) and
(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
and define our class of DTMCs :: “’a dtmc set”, through
definition :: “’a dtmc set” where
where :: “’a lang 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 :
lemma : “
Here, :: “’a lang ’a lang” is Isabelle’s counterpart of taking the prefix-minimal part of a language :
definition :: “’a lang ’a lang” where “
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 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 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 in a triple to be zero on lists of length that are not in lists , as adding more conditions to a lemma breaks neither its proof nor its conclusion.
We now define as the class of MRMs, thus incorporating a reward function that acts on lists directly:
and thus directly specifying a reward function 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:
We now specify and , Isabelle’s counterparts of Def. 4.2 and Def. 4.3. For , we have:
The function is defined through an auxiliary function, so for understandability we specify it with a characterisation:
lemma :
“” “”
“ ”
We are now ready to formalise the path abstraction algorithm for MRMs, as follows:
definition :: “” where
“ ”
Then, the underlying DTMC of an MRM gets mapped to its abstraction after applying ; the new reward function is specified by mapping a path to the (conditional) expected reward on the abstract path defined by , 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 :
assumes “” “”
shows “”
lemma :
assumes “” “” “”
shows “”
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 be a DTMC, where is a finite set, , and is such that is in the right-hand set of (21), where we fix as the universal set of symbols. For simplicity, we omit the brackets for singleton languages. Spelled out, (1) there exists a finite set such that for all with ; (2) ; (3) for all ; (4) ; (5) for all and we have ; and (7) for all we have . Write for the abstracted DTMC , where , with not to be confused with the from condition (1). We are thus done if we can establish that satisfies conditions (1), , (7) as well. Condition (1) is satisfied by if we choose as our finite set, and then follows directly from (23). Conditions (2) and (3) for also follow immediately from (23). Condition (4) follows directly from (4) for and (23) combined. Condition (7) for follows immediately from how (23) specifies how behaves on languages. At this point, to prove that satisfies conditions (5) and (6), conceptual complexity diverges from proof engineering complexity. Condition (5) is established for as follows, in Abstr.thy/abstr_well_defined. Since satisfies (1), is a sum of finitely many numbers. For each such we have by (23), or, equivalently, by Def. 4.4. But the sum of the 's over these values of is where , as . We have as its components are contained in as well, and we may apply Thm. 5.1 to establish that and hence satisfies condition (5). Condition (6) is then tackled as follows: if and are such that , we have for each where .7 Then, proving comes down to proving
which holds because , most of whose foundation we mechanise in Freemonoid.thy/ltappend_lminpfx_vimage_red. Indeed: converges on because is contained in a monoid on a finite set and all its words start with the first symbol of . We may thus use our variant of Tonelli’s theorem for non-negative real-valued functions—Thm. 5.2—applied to and —and the convergence result Thm. 5.1 for the languages , , and , which is applicable because the three languages start with the first symbol of , , and , respectively (note that these words are non-empty by assumption) and are contained in . The edge cases and are conceptually trivial and also do not pose further mechanisation challenges.
Theorem 5.1 (Convergence Lemma I: Problang.thy/has_csp_finite-confinable-substoch). Given such that there exist and and a finite such that and , a function satisfying (1),,(7) in the previous proof outline has the property that converges to a real number in .
Proof. Conceptually, this follows by monotonicity of convergence of non-negative functions, combined with the observation that in case is finite, which follows by induction on the depth of , i.e. the maximum length of a word in . In Isabelle, one needs to work out these connections explicitly. We first establish, in Problang.thy/is_ltree_substoch, that with the additional assumption that is finite, by induction on the depth of . The key idea is that chopping off the final symbols of the words in of maximum length yields of another language with depth one less than that of ; by grouping paths we thus establish , and we can reach all the way down to the base case . Then, to prove that converges to a real number in , we use Isabelle’s nonneg_bdd_above_summable_on lemma to prove that converges at all, taking as preconditions that 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 is easy.
Theorem 5.2 (Tonelli’s Theorem for non-negative functions: Problang.thy/double_sum). Let be a function from a set to the non-negative reals, such that converges on to a value :
Suppose that is a partition of , where is an index set (possibly infinite). Then,
Proof. This is Tonelli’s theorem for non-negative numbers. HOL-Analysis provides this result for sums over -types (has_sum_SigmaD), but our language decompositions are disjoint unions; rather than reindexing them as -types, we prove the union version directly from the bounded partial sums of non-negative functions. We first prove that for every finite , which is done via finite set induction on ; 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.
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 with . We extend the spirit of the proof outline of Thm. 4.1. Write , , and —which is due to Def. 4.5. Due to Thm. 4.1 we already know that is a DTMC. We thus need to verify, conforming to (22), that (1) whenever satisfies or , and (2) for all and for which we have . The fact that condition (1) holds for is immediately due to (24). Condition (2) is established to hold for as follows. Write again, for . We first consider the case that and are non-empty and (which implies ). Then, , , and ultimately , because we have from Thm. 4.1. We thus wish to prove
Using the property we rewrite the first sum as
which is possible as and , which we also mechanise, so that we may apply and because 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 of the form for , the sum converges in case is of the following special form: , where , which is the number of times appears as an edge in the path —cf. the formal definition of factor occurrence in § 2.1. Such sums are expected visiting times of the transition , whose convergence we prove in Thm. 5.3. It is not (too) hard to prove that for general we have the identity , and we have expressed as a linear combination of the values of on the two-state factors of , 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 range over their indexing sets in (26), we have , we may thus express each of as a linear combination of the values for . Then, the convergence result Thm. 5.3 can be pushed to transform (26) for the special case is of the form (where ) 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 and , follows. The remaining edge cases for and are easy, both conceptually and in proof engineering complexity.
Theorem 5.3 (Convergence Lemma II: Problang.thy/evt_summable_vimage_red_all). Let . Let satisfy the defining conditions of (21). Let be a finite set of symbols. Write . Let . Then, the following sum converges:
Proof. Since the terms of (27) are non-negative, our goal comes down to giving a proper upper bound on the sum. Intuitively, as becomes larger, probabilities of
(added) transitions are multiplied while new occurrences of are only added, and we either “leak” probability constantly when looping through or the language is finite or the probabilities of paths are zero beyond visiting as a transition more than once. We proceed by a case distinction on . For , is finite and the sum in (27) trivially converges. For with and , we proceed with reverse induction on . The case comes down to proving that the sum of (27) converges for , which we prove in a separate lemma. Now, if (27) converges for some , let us prove that this is the case if we replace by where and . Since , we can write where and . Then, we have as our new . Since and and and (27) converges for by the induction hypothesis, we may use Thm. 5.4 applied to and and the fact that (27) converges for the two-letter word . This is mechanised in Problang.thy/evt_summable_vimage_red 2. The latter fact is seen as follows. Following the characterisation (15), is infinite only if , in which case . If , then for all and we have convergence. The interesting case is thus . Defining , which intuitively is the set of all states in such that is reachable from a path starting in moving through , with positive probability, we look at two cases. If , then one can show that for all with we have and we have again convergence. For , we have by definition of and thus the set is non-empty, as , as . Let be of minimal length, and define the language
Clearly, because . Now, is a language contained in the free monoid on a finite set and has a common starting point , so that we may use Thm. 5.1 to conclude that . Since (because is of minimal length), we can use to deduce that if we set . We now prove that for , which comes with its own set of mechanisation challenges that we do not elaborate on here. It thus follows that, for , the sum in (27) can be bounded as
and this upper bound converges because , and does so to , which is a standard result in undergraduate calculus and real analysis.
Theorem 5.4 (Problang.thy/evt_summable_path_concatenation). Given , converges if and do (to, say, and , respectively), whenever and and there exist such that and .
Proof. The trick is to prove that for every finite we have ; applying the standard machinery from the nonneg_bdd_above_summable_on and infsum_nonneg_is_SUPREMUM_real lemmas again proves that converges.
Mechanising Monotonic Absorption
We prove Thms. 4.2 and 4.4, the monotonic absorption properties. Their Isabelle counterparts are, respectively:
lemma :
assumes “” “” “”
shows “” (32)
lemma :
assumes “” “” “”
“” shows “
” (33)
Proof outline of Thm. 4.2. We follow the pen-and-paper proof in [11 App. B]. Thus, let be a DTMC, and let . Write , , and for the abstractions , , and , respectively. To prove , it thus suffices to prove . We fix an and focus on the case (the edge cases are easy to verify). Working out the summation details for and , repeatedly applying the convergence lemma Thm. 5.1, gives
where for we write and . We prove
whose foundation we mechanise in Freemonoid.thy/lminpfx_monab. Then, we establish from (29) and (30), after applying Thm. 5.2 again, this time for and .
Proof outline of Thm. 4.4. Take the notation for , , and in the previous proof outline—that of Thm. 4.2, and write , , , and for MRMs such that , , and . By Thm. 4.2, we already have . We are thus left with establishing that . Analogously to (the proof of) Thm. 4.2, working out sums for and (for the substantial, non-edge case for ) gets us to a to-be-proven equality relating a double sum, coming from the side of , to a single sum, coming from the side of , which again is resolved by the identity , 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.
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 .
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 . Let us call the respective MRMs and . Both states in are reachable from the outside in one step, thus . It follows that, in obtaining from , only the transitions between states in are removed, and new transitions from to the set of states outside of reachable from in one step—namely, —are introduced, which, according to the characterisation in (16), get probabilities equal to the probabilities of the sets
with respect to the transition probability function of the old MRM , which evaluate to
where we have used the well-known identity for the geometric series for , applied to .
Now, for the rewards for those newly introduced transitions, let us consider the path set in for the transition in MRM . The paths , , etc. have probabilities and rewards
so that the reward for this transition in times its probability becomes
so that its reward becomes , where we have used the standard identity for , applied to . 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 —which is similar to the previous abstraction, exploiting the closed forms for and —and then over the full set of non-terminal states . 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
Indeed: since we have
Since as well, the latter is equal to , and the “biggest” set absorbs all other state sets.
References
- [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]Á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]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]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]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]Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press (2008)
- [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]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]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]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]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]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]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]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]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]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]Royden, H.L., Fitzpatrick, P.: Real Analysis. Pearson modern classic, Pearson, New York, NY, 4th edn. (2018)
- [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
