Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains

Timm Spork✉, Christel Baier, Joost-Pieter Katoen, Sascha Klüppelholz, Jakob Piribauer · 2025

Read Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains by Timm Spork✉, Christel Baier, Joost-Pieter Katoen, Sascha Klüppelholz, Jakob Piribauer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15587.txt.

Introduction

Timm Spork, Christel Baier, Joost-Pieter Katoen, Sascha Klüppelholz, and Jakob Piribauer wrote this 2025 theory paper. Their subject is how to tell when two random, time-based systems behave almost the same. Such systems are used to model things like computer networks and chemical reactions that change over time.

The authors define a new kind of near match that allows two separate limits. One limit covers the odds of each step, and the other covers how fast states are left behind. They prove basic facts about the idea and bound how far apart two matched systems can drift. The bounds cover the chance of reaching a target state in a set time.

Catalog record

CREATORTimm Spork✉, Christel Baier, Joost-Pieter Katoen, Sascha Klüppelholz, Jakob Piribauer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE170 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15587

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains Timm Spork✉, Christel Baier, Joost-Pieter Katoen, Sascha Klüppelholz, Jakob Piribauer Abstract We introduce ( ε , δ ) (\varepsilon,\delta) -bisimulation, a novel type of approximate probabilistic bisimulation for continuous-time Markov chains. In contrast to related notions, ( ε , δ ) (\varepsilon,\delta) -bisimulation allows the use of different tolerances for the transition probabilities ( ε \varepsilon , additive) and total exit rates ( δ \delta , multiplicative) of states. Fundamental properties of the notion, as well as bounds on the absolute difference of time- and reward-bounded reachability probabilities for ( ε , δ ) (\varepsilon,\delta) -bisimilar states, are established. 1 Introduction Continuous-time Markov chains (CTMCs) are a prominent probabilistic model in various application fields, e.g., reliability engineering, systems biology, modeling of chemical reactions, and performance evaluation. CTMCs are state-based models whose transitions yield a discrete probability distribution over states—as in discrete-time Markov chains (DTMCs)—while the state residence times are governed by exponential distributions. Various model-checking approaches for CTMCs exist [ 7 , 11 , 22 , 63 ] and are supported by tools such as PRISM [ 40 ] and Storm [ 34 ] . CTMC model checking is used to analyze, e.g., stochastic Petri nets [ 6 ] , fault trees [ 8 , 61 ] , biological systems [ 41 , 46 ] , and chemical reactions [ 2 , 4 ] . The central issue in CTMC model checking is computing timed reachability probabilities: what is the probability to reach a set of goal states within a given deadline from a given start state? The reliability of a fault tree, or the probability that all molecules have been catalyzed within two days, are instances of this question. Computing timed reachability probabilities reduces to computing transient probabilities in a uniformized CTMC, i.e., a CTMC in which the state residence times are “normalized” [ 13 ] . This method is quite efficient, numerically stable, and scales to CTMCs with millions of states. In practical applications, however, transition probabilities and state residence time distributions—defined by exit rates—are usually not known exactly. Component failure rates in fault trees are vulnerable to environmental conditions, and reaction rates of molecules are obtained experimentally. This raises the question whether CTMC model-checking results are robust w.r.t. perturbations of their stochastic aspects. The aim of this paper is to investigate to what extent transition probabilities and exit rates in a given CTMC can be altered while ensuring that timed reachability probabilities are preserved up to a small tolerance \theta . To this end we define the novel notion of (\varepsilon,\delta) -bisimulation on CTMCs, investigate its fundamental properties and derive bounds for timed reachability probabilities. The results yield under which (absolute) \varepsilon -tolerance on transition probabilities and (relative) \delta -tolerance on exit rates, timed reachability probabilities are close up to \theta . This enables, e.g., to determine the maximal tolerances in components’ failure rates while ensuring the fault tree’s (i.e., overall systems’) reliability. Our notion generalizes strong probabilistic bisimulation [ 19 ] (also known as lumpability) that preserves timed reachability probabilities exactly. Let us illustrate the conceptual difference of perturbing exit rates and transition probabilities separately in (\varepsilon,\delta) -bisimulations compared to existing notions such as \tau -quasi-lumpability (also known as near-lumpability) [ 19 , 29 , 30 ] that consider transition rates , i.e., products of exit rates and transition probabilities. s_{0} s_{1} g f \mathcal{M}_{1}\colon 10 1 1 10 \emptyset \emptyset \{\text{fail}\} \{\text{goal}\} s_{0} s_{1} g f \mathcal{M}_{2}\colon 10 1 1 11 \emptyset \emptyset \{\text{fail}\} \{\text{goal}\} s_{0} s_{1} g f \mathcal{M}_{3}\colon 10 \frac{1}{10} 2 10 \emptyset \emptyset \{\text{fail}\} \{\text{goal}\} Figure 1 : Three CTMCs where the copies of the states can be related by a \tau -quasi-lumpability iff \tau\geq 1 . The numbers indicate the transition rates between states. Example 1 Consider the CTMCs in Figure 1 . The value attached to an arrow from state s to state s^{\prime} describes the transition rate R(s,s^{\prime}) between s and s^{\prime} , given as the product of the total exit rate E(s) of s and the probability P(s,s^{\prime}) to move from s to s^{\prime} . The colors of the states indicate their labels (also written next to the states). Note that the CTMCs \mathcal{M}_{1} and \mathcal{M}_{2} behave very similarly—in \mathcal{M}_{2} , the transition to f is only taken with a slightly higher rate, and the probability to reach the goal state g until time t is almost the same in the two models. The CTMCs \mathcal{M}_{1} and \mathcal{M}_{3} , however, behave very differently—reaching g until t is much less likely in \mathcal{M}_{3} because of the significantly lower rate R(s_{1},g) . A \tau -quasi-lumpability [ 19 , 29 , 30 ] is an equivalence relation such that related states have the same label and the total transition rates to move to any other equivalence class from related states differ by at most \tau . If we want to relate the states of \mathcal{M}_{1} with their copies in \mathcal{M}_{2} with a \tau -quasi-lumpability, \tau has to be at least 1 due to the change of the transition rate from s_{0} to f from 10 to 11 . For \tau=1 , however, we can also relate the states of \mathcal{M}_{1} with their copies in \mathcal{M}_{3} . Hence, \tau -quasi-lumpability does not allow us to capture the intuition that \mathcal{M}_{1} and \mathcal{M}_{2} behave similarly while \mathcal{M}_{1} and \mathcal{M}_{3} behave very differently. The central idea behind (\epsilon,\delta) -bisimulations is to decouple the changes of exit rates and transition probabilities of related states. In \mathcal{M}_{1} and \mathcal{M}_{2} from Figure 1 , the total exit rate E(s_{0})=\sum_{s^{\prime}}R(s_{0},s^{\prime}) of s_{0} changes by a factor of 1.05 from 20 to 21 , and the probability P(s_{0},f)=\frac{R(s_{0},f)}{E(s_{0})} to transition from s_{0} to f is 1/2 and 11/21 , respectively. The absolute change of transition probabilities and the relative change of exit rates is small, so the chains behave similarly. For \mathcal{M}_{1} and \mathcal{M}_{3} , however, P(s_{1},g) changes from 1/2 to 1/21 , a huge difference. In this way, (\epsilon,\delta) -bisimulation can express (dis)similarities of CTMCs in a more fine-grained manner than notions that consider the transition rates between states. Main Contributions. Our main contributions are the following: • We introduce (\varepsilon,\delta) -bisimulation for CTMCs, a novel type of approximate probabilistic bisimulation that allows an absolute tolerance of \varepsilon for the transition probabilities of related states, and a relative tolerance of \delta for their total exit rates. We prove that the union of all (\varepsilon,\delta) -bisimulations, called (\varepsilon,\delta) -bisimilarity, is an (\varepsilon,\delta) -bisimulation itself, that it is additive in \varepsilon and \delta , and that it coincides with strong bisimilarity [ 15 , 19 ] iff \varepsilon=\delta=0 . Moreover, we discuss how quasi-lumpability [ 19 , 29 , 30 ] and (\varepsilon,\delta) -bisimilarity relate, and show how to “split” (\varepsilon,\delta) -bisimilarity into (\varepsilon,0) - and (0,\delta) -bisimilarity, allowing an individual treatment of the parameters ( Section 3 ). • We derive bounds on the absolute difference of timed reachability probabilities of (\varepsilon,\delta) -bisimilar states by uniformizing the CTMC and applying a bound from [ 18 ] for the difference in finite horizon reachability probabilities of \varepsilon -bisimilar states of DTMCs [ 25 ] . The bounds are tight if \delta=0 ( Section

Read the complete text