On the Continuity of the Probabilistic Bisimilarity Distance
Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, Franck van Breugel · 2026
Read On the Continuity of the Probabilistic Bisimilarity Distance by Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, Franck van Breugel (2026) 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-2606-27209.txt.
Introduction
Fatmi and colleagues settle when a standard distance between probabilistic systems behaves continuously. The bisimilarity distance measures how differently two states of a labelled Markov chain can behave. Small wobbles in transition chances can make that distance jump, which threatens models fitted from real data. The authors earlier introduced robust bisimilarity as a route to continuity at distance zero. In 2026, necessity is the new question, in the full version of a conference work.
Robust bisimilarity proves both needed and enough at zero distance. Extending robustness beyond bisimilar pairs yields a complete account of continuity everywhere. A polynomial-time algorithm decides continuity from that account. Experiments show the decision step adds minimal cost over computing the distance itself. Practitioners using estimated transition chances gain a cheap check for when distance values can be trusted under noise.
Catalog record
| CREATOR | Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, Franck van Breugel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 122 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27209
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Continuity of the Probabilistic Bisimilarity Distance Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, Franck van Breugel Abstract The probabilistic bisimilarity distance provides a quantitative measure of behavioural difference for labelled Markov chains, but it may be discontinuous under perturbations of the transition probabilities. This lack of continuity undermines its applicability to empirically derived models, where transition probabilities are often approximations. Recently, we introduced robust probabilistic bisimilarity as a sufficient condition for continuity at distance zero. In this paper, we show that it is also a necessary condition, that is, two states are robustly probabilistic bisimilar if and only if their probabilistic bisimilarity distance is small for any small enough perturbation of the transition probabilities. We further extend robustness to non-bisimilar state pairs to establish a complete characterization for continuity of the probabilistic bisimilarity distance. Based on this characterization, we develop a polynomial time algorithm to decide continuity. Finally, we complement our theoretical contributions with an experimental evaluation demonstrating the proposed approach in practice. Our results show that the extra step of deciding continuity requires minimal additional cost when compared to computing the probabilistic bisimilarity distance. University of Oxford, Oxford, UK https://orcid.org/0000-0001-7899-8665Clarendon FundUniversity of Oxford, Oxford, UK https://orcid.org/0000-0003-4173-6877EPSRC grant EP/Z536179/1 University of Oxford, Oxford, UK https://orcid.org/0000-0003-4137-8862 York University, Toronto, Canada https://orcid.org/0009-0002-7320-1527Natural Sciences and Engineering Research Council of Canada ccs Theory of computation Logic and verification ccs Verification by model checking ccs Probabilistic computation keywords probabilistic model checking, labelled Markov chain, probabilistic bisimilarity distance † † runningtitle: On the Continuity of the Probabilistic Bisimilarity Distance † † runningauthor: S. Z. Fatmi, S. Kiefer, D. Parker, F. van Breugel † † copyright: Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, and Franck van Breugel † † relatedversion: This is the full version of a CONCUR 2026 paper [ 18 ] . † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Probabilistic bisimilarity (henceforth just bisimilarity ) is a concept of behavioural equivalence for probabilistic systems, such as labelled Markov chains. Kemeny and Snell [ 28 ] introduced the notion of lumpability for Markov chains and it was adapted to the setting of labelled Markov chains by Larsen and Skou [ 33 ] . Intuitively, two states of a labelled Markov chain are considered bisimilar if they have the same labels and they transition into the same equivalence classes with the same probabilities. Bisimilarity can be used to minimize the state space of a system by identifying and merging states that are behaviourally indistinguishable, which often reduces the time required to verify properties of the system [ 27 ] . However, since behavioural equivalences are sensitive to the exact values of the transition probabilities, Giacalone et al. [ 21 ] proposed using behavioural pseudometrics, a quantitative generalisation of behavioural equivalences, to capture the behavioural similarity of states in a probabilistic system. Rather than classifying states as either equivalent or inequivalent, the pseudometric maps each pair of states to a real value in the unit interval, thus also quantifying the behavioural difference between non-equivalent states. In probabilistic verification, the most widely studied example of such a behavioural pseudometric is the probabilistic bisimilarity distance (henceforth just bisimilarity distance ), introduced by Desharnais et al. [ 10 ] , which quantitatively generalises bisimilarity. The lower the distance between two states, the less difference in their behaviour, and two states have distance zero if and only if they are bisimilar. {subcaptionblock} s t u \frac{0.5}{10}{\color[rgb]{1,0.1,0.14}+\varepsilon} \frac{9.5}{10}{\color[rgb]{1,0.1,0.14}-\varepsilon} 1 \frac{1}{10} \frac{9}{10} 1 {\color[rgb]{1,0.1,0.14}\varepsilon} 1 1 1{\color[rgb]{1,0.1,0.14}-\varepsilon} Figure 1: A family of labelled Markov chains for \varepsilon\in[0,\frac{9.5}{10}] . The state labels are represented by colours. {subcaptionblock} 0 0.5 1 0 0.5 1 \varepsilon \delta_{\tau_{\varepsilon}}(s,t) 0 0.5 1 0 0.5 1 \varepsilon \delta_{\tau_{\varepsilon}}(s,u) Figure 2: An illustration of the distances between the state pairs (s,t) and (s,u) , respectively. When \varepsilon=0 , then the distance between these pairs is 0.05. As \varepsilon increases, the distance between s and t increases proportionally, whereas the distance between s and u jumps up to 1 . Figure 3: A motivating example. Example 1 . The bisimilarity distance is based on a variation of Larsen and Skou’s probabilistic modal logic [ 8 , 31 , 33 , 34 ] . A formula \varphi of this logic assigns to each state s of a labelled Markov chain a numerical value [\![\varphi]\!](s)\in[0,1] . For example, consider the labelled Markov chain in Figure 3 when \varepsilon=0 . The states s and t have a bisimilarity distance of 0.05. Then it follows [ 5 , Equation 2.3] that |[\![\varphi]\!](s)-[\![\varphi]\!](t)|\leq 0.05 , where \varphi ranges over all formulas. Thus, the bisimilarity distance bounds the maximal difference in logical observations between states. This is relevant for model checking. Suppose we are interested in computing the probability of eventually reaching a state labelled with orange . This property can be expressed as the quantitative mu-calculus formula \varphi=\mu V.\,\textit{orange}\vee\textrm{next}(V) . For efficiency one might want to approximate these values [\![\varphi]\!] , up to some acceptable error threshold, say 0.1 . In this case, for states s and t , it suffices to compute [\![\varphi]\!](s) only. The same holds for every formula \varphi of the logic. Similarly, since states s and u also have a bisimilarity distance of 0.05, it follows that |[\![\varphi]\!](s)-[\![\varphi]\!](u)|\leq 0.05<0.1 , for all \varphi . Hence, for states s and u , it suffices to compute [\![\varphi]\!](s) only as well, speeding up model checking. \lipicsEnd However, as recognised by Jaeger et al. [ 25 ] , the bisimilarity distance is sometimes not continuous. Small changes in the transition probabilities can lead to unexpected and abrupt changes in behaviour between two states. This is especially concerning when relying on bisimilarity as a measure of system equivalence for empirically derived models, where transition probabilities are often approximated from experimental data [ 13 , 35 , 37 , 40 , 42 ] . It may be dangerous to merge bisimilar states if the transition probabilities are not known precisely, as the distance may jump up. In such settings, continuity analysis provides a way to assess the sensitivity of the bisimilarity distance to perturbations. If the distance is continuous, then sufficiently small errors in the transition probabilities result in only small changes in the distance; if it is discontinuous, arbitrarily small perturbations may cause a non-negligible increase in the distance, indicating that the apparent similarity of two states may not be robust to uncertainty in the model. More recently, in our prior work [ 17 ] , we introduced a new notion of probabilistic equivalence, namely robust probabilistic bisimilarity (henceforth just robust bisimilarity ). Our main result showed that this definition ensures the continuity of the bisimilarity distance function under perturbations of the transition probabilities. However, several fundamental questions remain unanswered. First, although we conjectured in [ 17 ] that robust bisimilarity is not only a sufficient but also a necessary condition for continuity, this was left open. Second, our analysis in [ 17 ] is