💻 computer science

On the Continuity of the Probabilistic Bisimilarity Distance

This paper establishes that robust probabilistic bisimilarity is both a necessary and sufficient condition for the continuity of probabilistic bisimilarity distances under transition probability perturbations, thereby enabling a polynomial-time algorithm to decide continuity with minimal computational overhead.

Original authors: Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, Franck van Breugel

Published 2026-06-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Syyeda Zainab Fatmi, Stefan Kiefer, David Parker, Franck van Breugel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a quality control inspector for a fleet of self-driving cars. Each car is a "probabilistic system," meaning it doesn't always do the exact same thing; sometimes it turns left, sometimes right, based on a set of odds (probabilities).

To check if two cars are essentially the same, engineers use a tool called Probabilistic Bisimilarity. Think of this as a "behavioral twin test." If two cars have the same labels (e.g., both are "Sedan") and they react to traffic lights with the exact same probabilities, they are considered "bisimilar" (twins).

However, in the real world, we rarely know the exact odds. We estimate them from data. Maybe Car A turns left 50% of the time, but our measurement says 49.9%. This is where things get tricky.

The Problem: The "Glass House" Effect

The paper introduces a concept called the Bisimilarity Distance. Instead of just saying "Same" or "Different," this tool gives a score from 0 to 1.

0 means they are perfect twins.
1 means they are completely different.
0.05 means they are very similar.

The problem is that this distance score can be discontinuous. Imagine a glass house that looks perfectly stable until you tap it with a tiny pebble, and suddenly the whole thing shatters.

In the paper's example, two cars might look almost identical (distance 0.05). But if you change their turning probability by a microscopic amount (a tiny "perturbation"), their behavior score might suddenly jump to 1.0. They go from "almost twins" to "total strangers" instantly. This is dangerous for engineers because if they rely on the "0.05" score to simplify their models, a tiny measurement error could make their entire safety analysis wrong.

The Solution: "Robust" Twins

The authors previously invented a stricter test called Robust Probabilistic Bisimilarity.

Standard Bisimilarity: "These cars are twins right now."
Robust Bisimilarity: "These cars are twins and they will stay twins even if we nudge their probabilities slightly."

Think of it like a marriage.

Standard: "They are a couple today."
Robust: "They are a couple, and they will stay a couple even if they have a small argument or a bad day."

The Big Discovery

In this paper, the authors prove two major things:

The "If and Only If" Rule: They proved that Robust Bisimilarity isn't just a good way to find stable twins; it is the only way.
- If two states are robustly bisimilar, their distance score will stay smooth and stable when you nudge the probabilities.
- If they are not robustly bisimilar, their distance score is a "glass house"—it will shatter (jump) with the slightest nudge.
- Analogy: You can't have a "stable glass house." If it's not robust, it's fragile.
The Universal Check: They extended this logic to all pairs of states, not just the ones that are currently twins. They created a mathematical rule to determine if any two states have a stable distance score, even if they aren't perfect twins to begin with.

The Tool: A Fast Calculator

The authors didn't just stop at theory. They built a polynomial-time algorithm.

What does that mean? It means they wrote a computer program that can check for this "stability" very quickly.
The Cost: They tested this on real-world models (like randomized algorithms and traffic systems). They found that checking for this stability adds almost no extra time to the calculation. It's like checking if a bridge is "robust" takes the same amount of time as just measuring its length.

The Takeaway

The paper solves a critical reliability issue. It tells engineers:

"Don't just trust that two systems are similar because their numbers look close."
"Use our new 'Robust' test. If they pass, you know their similarity score won't jump unexpectedly due to tiny measurement errors."
"And don't worry, checking this is fast and cheap."

In short, they turned a fragile, unpredictable measurement tool into a sturdy, reliable one, and gave everyone a fast way to use it.

Technical Summary: On the Continuity of the Probabilistic Bisimilarity Distance

1. Problem Statement

Probabilistic bisimilarity is a standard behavioral equivalence for labelled Markov chains (LMCs), used to minimize state spaces and verify system properties. However, exact bisimilarity is brittle: small perturbations in transition probabilities can cause states to lose equivalence entirely. To address this, the probabilistic bisimilarity distance ( $\delta_\tau$ ) was introduced as a quantitative measure of behavioral difference, where $\delta_\tau(s, t) = 0$ iff $s$ and $t$ are bisimilar.

A critical limitation of this metric is its potential discontinuity. As noted by Jaeger et al. [25], small changes in transition probabilities can lead to abrupt, non-negligible jumps in the distance between states. This lack of continuity undermines the metric's applicability to empirically derived models, where transition probabilities are often approximations of experimental data. If the distance is discontinuous, relying on it to merge states or approximate model checking results can be dangerous, as the "apparent similarity" may not be robust to uncertainty.

In prior work [17], the authors introduced robust probabilistic bisimilarity ( $\simeq$ ) as a sufficient condition for the continuity of the bisimilarity distance for bisimilar state pairs. However, two fundamental questions remained open:

Is robust bisimilarity also a necessary condition for continuity?
How can one characterize and decide continuity for non-bisimilar state pairs?

2. Methodology and Theoretical Framework

The paper addresses these questions by extending the theoretical framework of couplings and policies on the product state space $S \times S$ .

2.1 Preliminaries

The authors utilize the standard definition of bisimulation based on couplings (Definition 3). The bisimilarity distance $\delta_\tau$ is defined as the least fixed point of a function $\Delta_\tau$ , which minimizes the expected distance over all couplings of transition distributions.
Crucially, the distance is characterized via policies (Definition 10). A policy $P$ induces a Markov chain on $S \times S$ . The distance $\delta_\tau(s, t)$ corresponds to the minimum probability of reaching the set of pairs with different labels ( $S^2_1$ ) from $(s, t)$ in the induced chain (Proposition 11).

2.2 Robust Bisimilarity and Continuity

Robust bisimilarity ( $s \simeq t$ ) is defined as the existence of a policy $P$ such that the probability of reaching the diagonal set $S^2_\Delta$ (where states are identical) from $(s, t)$ is 1.

Previous Result (Theorem 13): If $s \simeq t$ , then $\delta_{(\cdot)}(s, t)$ is continuous at $\tau$ .
New Contribution (Theorem 14): The authors prove the converse: for bisimilar states ( $s \sim t$ ), continuity of the distance function holds if and only if $s \simeq t$ . This establishes robust bisimilarity as a necessary and sufficient condition for continuity within the set of bisimilar pairs.

2.3 General Characterization for Arbitrary Pairs

The paper extends the analysis to arbitrary state pairs (including non-bisimilar ones).

Theorem 17: For any $s, t \in S$ $s, t \in S$ , the distance function $\delta_{(\cdot)}(s, t)$ $δ_{(\cdot)} (s, t)$ is continuous at $\tau$ $τ$ if and only if there exists a policy $P$ $P$ such that the probability of reaching $S^2_\Delta$ $S_{Δ}^{2}$ from $(s, t)$ $(s, t)$ is exactly $1 - \delta_\tau(s, t)$ $1 - δ_{τ} (s, t)$ .
- This condition implies that the "loss" in reaching the diagonal (which would increase the distance to 1) is exactly balanced by the distance value itself.
- If no such policy exists (i.e., the maximum probability of reaching the diagonal is strictly less than $1 - \delta_\tau(s, t)$ ), the distance is discontinuous.

2.4 Algorithmic Decision Procedure

Based on Theorem 17, the authors develop Algorithm 1 to decide continuity for all pairs of states in polynomial time.

Mechanism: The algorithm computes the set of discontinuous pairs by iteratively identifying pairs that cannot reach the "robust" set without passing through a "bad" set (pairs that are bisimilar but not robustly so, or pairs that inevitably lead to label mismatches).
Fixed Point Computation: The algorithm uses monotone functions $A$ and $B$ on the lattice of state pairs. It computes the least fixed point $\alpha$ (discontinuous pairs) and the greatest fixed point $\beta$ (continuous pairs).
Complexity: The check for optimal couplings (line 6 of Algorithm 1) is reduced to a minimum cost maximum flow problem (Proposition 25), solvable in polynomial time. The overall algorithm runs in polynomial time relative to the state space size.

3. Key Contributions

Necessity of Robust Bisimilarity: The paper proves that robust probabilistic bisimilarity is not just sufficient but also necessary for the continuity of the bisimilarity distance for bisimilar state pairs, settling a conjecture from [17].
Complete Characterization: The authors provide a complete theoretical characterization of continuity for all pairs of states (bisimilar or not) via Theorem 17, linking continuity to the existence of a specific policy maximizing reachability to the diagonal.
Polynomial-Time Decision Algorithm: A new algorithm is presented that decides continuity for all state pairs in polynomial time.
Experimental Validation: The algorithm was implemented in the PRISM model checker. Experiments on the Quantitative Verification Benchmark Set (QVBS) and randomized Java algorithms (via jpf-probabilistic) demonstrate that deciding continuity incurs minimal overhead compared to computing the distance itself. In many cases, the continuity check is significantly faster.

4. Results and Experimental Evaluation

The experimental evaluation focused on benchmarks where the minimized models under traditional bisimilarity and robust bisimilarity differ (indicating potential discontinuity).

Efficiency: For most benchmarks, the time required to decide continuity was less than or comparable to the time required to compute the bisimilarity distance. For example, in the oscillators benchmark, the distance computation took ~5 seconds, while continuity checking took ~0.002 seconds.
Trivial Cases: When the distance is continuous for all pairs (e.g., when traditional and robust bisimilarity coincide), the algorithm terminates almost immediately.
Practicality: The results confirm that the "extra step" of verifying continuity is computationally feasible and provides a robustness guarantee for models with uncertain transition probabilities.

5. Significance and Claims

The paper claims to close the theoretical gaps regarding the continuity of probabilistic bisimilarity distance. By proving that robust bisimilarity is the exact condition for continuity in the bisimilar case and providing a general characterization for all pairs, the work enables practitioners to:

Assess Robustness: Determine if the behavioral similarity between two states is stable under small perturbations of transition probabilities.
Safe Model Reduction: Safely merge states in empirically derived models only when continuity is guaranteed, avoiding the risk of "distance jumps" that could invalidate model checking results.
Efficient Verification: Integrate continuity checks into existing verification workflows with negligible performance cost.

The authors note that while the current work establishes decidability and characterization, future work will aim to provide quantitative bounds on how much the distance can increase under perturbations and investigate continuity under graph-structure-preserving perturbations.