Behavioural equivalences for continuous-time Markov processes

Linan Chen, Florence Clerc, Prakash PanangadenMath. Struct. Comput. Sci 2023 · DOI

Abstract: This paper establishes a rigorous theoretical foundation for determining when two continuous-time stochastic processes exhibit identical behavior. By shifting the focus from discrete state transitions to cadlag trajectories, the authors unify relational, categorical, and game-theoretic perspectives on behavioral equivalence for Feller-Dynkin processes.

The Challenge of Continuous Time

In computer science, bisimulation is the gold standard for proving two systems are functionally identical. In discrete-time systems, this is typically defined inductively: if two states are equivalent now, they must transition to equivalent states in the "next step."

However, continuous-time systems—such as particles undergoing Brownian motion or complex chemical reactions—do not have a "next step." Evolution is a fluid flow through time, where the state can change at every infinitesimal moment. Previous research often simplified this by focusing on "jump processes," which remain in a state for a random duration before jumping. This paper addresses the more complex problem of processes where the traditional inductive definition of bisimulation vanishes due to the lack of discrete steps.

Methodological Framework: Feller-Dynkin Processes

The authors utilize Feller-Dynkin (FD) processes as their primary mathematical framework. These encompass a broad class of Markov processes, including Brownian motion and its variants. To bridge the gap between discrete and continuous time, the authors introduce several key methodological shifts:

  • From Steps to Trajectories: Instead of single transitions, equivalence is defined based on the probability of a process following a specific cadlag trajectory (a path that is right-continuous with left limits).
  • Categorical Framework: The authors define FD-homomorphisms—functions that preserve process dynamics—and demonstrate that behavioral equivalence can be modeled as a cospan. This allows two different processes to be "glued" together through a shared quotient system.
  • Game Theory: The research adapts the "Spoiler-Duplicator" game. In this continuous-time version, the Spoiler challenges the Duplicator by selecting sets of trajectories, and the Duplicator must find matching trajectories that maintain identical atomic observations.

Hierarchy and Unification of Equivalences

A central contribution of the paper is the establishment of a clear hierarchy between different types of behavioral equivalences. As shown in the figure below, the authors prove that the categorical view (cospans) and the relational view (bisimulation) are equivalent for this class of processes.

Hierarchy and relationships between behavioral equivalences and their characterizations.

The paper establishes that Bisimulation is the strongest form of equivalence, implying Temporal Equivalence, which in turn implies Trace Equivalence. While trace equivalence only considers what an external observer sees, bisimulation accounts for the underlying "branching" structure of stochastic evolution. Furthermore, the authors demonstrate that if a system possesses a group of symmetries, the equivalence relation defined by those symmetries constitutes a bisimulation.

Key Results and Future Directions

The authors validate their theory by demonstrating that their continuous-time definitions perfectly recover standard discrete-time bisimulation when a timer is added to force transitions at unit intervals. A major categorical result is the proof that the category of FD-processes has pushouts, meaning that for any two behaviorally equivalent systems, there exists a "minimal" system representing their shared behavior.

While the theory is robust, the authors acknowledge the "measurability monster" inherent in continuous-time mathematics, where crucial elements like "hitting times" are not always mathematically well-behaved. Future work is suggested to move from binary equivalence toward bisimulation metrics, which would quantify the degree of difference between two processes—a vital tool for real-world engineering and system approximation.

Summary updated

BibTeX
@article{chen2023behavioural,
  author = {Linan Chen and Florence Clerc and Prakash Panangaden},
  title = {{Behavioural equivalences for continuous-time Markov processes}},
  journal = {Math. Struct. Comput. Sci.},
  year = {2023},
  doi = {10.1017/s0960129523000099},
}
Figure