A behavioural pseudometric for continuous-time Markov processes
Linan Chen, Florence Clerc, Prakash Panangaden · 2025
Read A behavioural pseudometric for continuous-time Markov processes by Linan Chen, Florence Clerc, Prakash Panangaden (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-2501-13008.txt.
Introduction
Linan Chen, Florence Clerc, and Prakash Panangaden build a distance measure for systems that evolve in continuous time, in a 2025 paper. Engineers model such systems, from drifting particles to jumping queues, as continuous-time Markov processes. To compare two processes, one wants a behavioral distance: close means hard to tell apart by watching.
Discrete-time versions of this metric exist, built on step-by-step jumps. The trio lift the idea to continuous flow, where states glide, jump, or both. They define the distance two ways, as a fixed point of an operator and through a real-valued logic, and prove the two agree. The result metrizes behavior for a broad class of timed systems.
Catalog record
| CREATOR | Linan Chen, Florence Clerc, Prakash Panangaden |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A behavioural pseudometric for continuous-time Markov processes Linan Chen, Florence Clerc, Prakash Panangaden Abstract In this work, we generalize the concept of bisimulation metric in order to metrize the behaviour of continuous-time processes. Similarly to what is done for discrete-time systems, we follow two approaches and show that they coincide: as a fixpoint of a functional and through a real-valued logic. The whole discrete-time approach relies entirely on the step-based dynamics: the process jumps from state to state. We define a behavioural pseudometric for processes that evolve continuously through time, such as Brownian motion or involve jumps or both. 1 Introduction Bisimulation is a concept that captures behavioural equivalence of states in a variety of types of transition systems. It has been widely studied in a discrete-time setting where the notion of a step is fundamental. An important and especially useful further notion is that of bisimulation metric which quantifies “how similar two states are”. Most of the theoretical work that exists is on discrete time but a growing part of what computer science allows us to do is in real-time: robotics, self-driving cars, online machine-learning etc. A common solution is to discretize time, however it is well-known that this can lead to errors that are hopefully small but that may accumulate over time and lead to vastly different outcomes. For that reason, it is important to have a continuous-time way of quantifying the error made. Bisimulation [ 22 , 25 , 28 ] is a fundamental concept in the theory of transition systems capturing a strong notion of behavioural equivalence. The extension to probabilistic systems is due to Larsen and Skou [ 21 ] ; henceforth we will simply say “bisimulation” instead of “probabilistic bisimulation”. Bisimulation has been studied for discrete-time systems where transitions happen as steps, both on discrete [ 21 ] and continuous state spaces [ 3 , 12 , 13 ] . In all these types of systems, a crucial ingredient of the definition of bisimulation is the ability to talk about the next step . This notion of bisimulation is characterized by a modal logic [ 21 ] even when the state space is continuous [ 12 ] . Some work had previously been done in what are called continuous-time systems, see for example [ 2 ] , but even in so-called continuous-time Markov chains there is a discrete notion of time step ; it is only that there is a real-valued duration associated with each state that leads to people calling such systems continuous-time. They are often called “jump processes” in the mathematical literature (see, for example, [ 26 , 31 ] ), a phrase that better captures the true nature of such processes. Metrics and equivalences for such processes were studied by Gupta et al. [ 18 , 19 ] . The processes we consider have continuous state spaces and are governed by a continuous-time evolution, a paradigmatic example is Brownian motion. When approximating such processes by discrete-time processes, entirely new phenomena and difficulties manifest themselves in this procedure. For example, even the basic properties of trajectories of Brownian motion are vastly more complicated than the counterparts of a random walk. Basic concepts like “the time at which a process exits a given subset of the state space” becomes intricate to define. Notions like “matching transition steps” are no longer applicable as the notion of “step” does not make sense. In [ 8 , 9 , 10 ] , we proposed different notions of behavioural equivalences on continuous-time processes. We showed that there were several possible extensions of the notion of bisimulation to continuous time and that the continuous-time notions needed to involve trajectories in order to be meaningful. There were significant mathematical challenges in even proving that an equivalence relation existed. For example, obstacles occurred in establishing measurability of various functions and sets, due to the inability to countably generate the relevant \sigma -algebras. Those papers left completely open the question of defining a suitable pseudometric analogue, a concept that would be more useful in practice than an equivalence relation. Previous work on discrete-time Markov processes by Desharnais et al. [ 14 , 16 ] extended the modal logic characterizing bisimulation to a real-valued logic that allowed to not only state if two states were “behaviourally equivalent” but, more interestingly, how similarly they behaved. This shifts the notion from a qualitative notion (an equivalence) to a quantitative one (a pseudometric). Other work also on discrete-time Markov processes by van Breugel et al. [ 29 ] introduced a slightly different real-valued logic and compared the corresponding pseudometric to another pseudometric obtained as a terminal coalgebra of a carefully crafted functor. We also mention in this connexion the work by Ferns et al. on Markov Decision Processes and the connexion between bisimulation and optimal value functions [ 17 ] . In this work, we are looking to extend the notion of bisimulation metric to a behavioural pseudometric on continuous-time processes. Very broadly speaking, we are following a familiar path from equivalences to logics to metrics. However, it is necessary for us to redevelop the framework and the mathematical techniques from scratch. Indeed, a very important aspect in discrete-time is the fact that the process is a jump process, “hopping” from state to state. This limitation also applies to continuous-time Markov chains. In our case, we want to cover processes that evolve through time. A standard example would be Brownian motion or other diffusion processes (often described by stochastic differential equations). As one will see throughout this work, there are new mathematical challenges that need to be overcome. This means that the similarity between the pre-existing work on discrete-time and our generalization to continuous-time is only at the highest level of abstraction. Outline of the paper: The first two sections after the introduction are background. We will start by recalling some mathematical notions in Section 2 , introducing the continuous-time processes that we will be studying in Section 3 . A very brief overview of bisimulation metrics in discrete time can also be found in Appendix 0.A . In Section 4 , we will introduce a functional \mathcal{F} and define a pseudometric \overline{\delta} using this functional. We will also show that the pseudometric \overline{\delta} is a fixpoint of \mathcal{F} . In Section 5 , we will show that this pseudometric is characterized by a real-valued logic. We will further emphasize the novelty of this work wrt discrete time and summarize the obstacles that we had to overcome in Section 6 . We will provide some examples in Section 7 . Finally we will discuss the limitations of our approach and how it relates to previous works in Section 8 . 2 Mathematical background We assume the reader to be familiar with basic measure theory and topology. Nevertheless we provide a brief review of the relevant notions and theorems. Let us start with clarifying a few notations on integrals: Given a measurable space X equipped with a measure \mu and a measurable function f:X\to\mathbb{R} , we can write either \int f~\mathrm{d}\mu or \int f(x)~\mu(\mathrm{d}x) interchangeably. The second notation will be especially useful when considering a Markov kernel P_{t} for some t\geq 0 and x\in X :