Behavioural pseudometrics for continuous-time diffusions

Linan Chen, Florence Clerc, Prakash PanangadenarXiv 2023 · DOI · arXiv

TL;DR

This paper extends the concept of behavioral equivalence (bisimulation) to continuous-time stochastic processes known as diffusions. By moving beyond simple "yes/no" equivalence, the authors develop two quantitative pseudometrics that measure how much two processes differ, using tools from optimal transport theory and real-valued modal logics.

What Problem Does This Paper Address?

In computer science, bisimulation is a gold standard for determining if two systems behave identically. Traditionally, this is studied in discrete-time systems where you can talk about the "next step." However, many real-world physical and financial systems are modeled as continuous-time diffusions (like Brownian motion), where there is no such thing as a "next step"—the state flows continuously.

Previous research established ways to say two such "flow" processes are equivalent, but equivalence is a brittle notion. In practice, two systems might not be identical but are "close enough." This paper addresses the need for behavioral pseudometrics: mathematical tools that provide a numerical distance between states based on their future behavior, allowing for a robust, quantitative analysis of continuous-time stochastic systems.

Methods

The authors propose two distinct ways to measure behavioral distance, both relying on Optimal Transport (Wasserstein distance) to compare probability distributions:

  1. The Kernel-Based Approach ($\mathcal{F}_c$): This functional compares the time-indexed family of Markov kernels. It looks at the probability distributions of where a process might be at any given time $t$ and takes the supremum over all time, applying a discount factor to ensure the math stays well-behaved.
  2. The Trajectory-Based Approach ($\mathcal{G}_c$): Instead of looking at snapshots in time, this approach compares the probability distributions over entire paths (trajectories) that the process might take.

To prove these metrics are meaningful, the authors use Fixpoint Theory. they show that their behavioral metrics are the least fixpoints of specific functionals. Furthermore, they provide a Logical Characterization by designing real-valued modal logics. They prove that the distance between two states measured by the logic (the difference in "test scores" the states achieve) is exactly equal to the distance measured by their proposed pseudometrics.

Datasets

As a theoretical paper in computer science and mathematics, this work does not use empirical datasets. Instead, it uses paradigmatic mathematical models of diffusions, such as Brownian motion, Geometric Brownian motion, and the Ornstein-Uhlenbeck process, to illustrate the theory.

Key Insights and Ideas

  • The "Next Step" Problem: In discrete systems, bisimulation is defined by what happens in the next discrete jump. In diffusions, the authors show you must instead look at the entire "flow" or the evolution of the probability density function over time.
  • Kernels vs. Trajectories: A major insight is that measuring distance based on where a process ends up at time $t$ (kernels) is fundamentally different from measuring distance based on the path it took to get there (trajectories). The paper shows these lead to two different behavioral metrics.
  • Discounting for Continuity: To handle the mathematical "heaviness" of continuous time, the authors introduce a discount factor ($c < 1$). This allows them to bound time intervals and maintain the continuity of the metrics, which is essential for the fixpoint iterations to converge.
  • Kantorovich Duality: The authors cleverly use the dual form of the optimal transport problem to link their metrics directly to the grammar of their modal logics.

Key Results

  • Fixpoint Existence: The authors successfully defined two behavioral pseudometrics ($\delta^c$ and $d^c$) and proved they are the least fixpoints of their respective functionals.
  • Logical Characterization: They proved that $\delta^c = \lambda^c$ and $d^c = \ell^c$, where $\lambda^c$ and $\ell^c$ are distances derived from two different real-valued modal logics. This means the metrics have a clear interpretation as the maximum difference in "observable properties" between two states.
  • Metric Hierarchy: The paper establishes that the trajectory-based metric is "finer" than the kernel-based metric ($\delta^c \leq d^c$), meaning it can distinguish between processes that the kernel-based metric might see as identical.

Limitations and Future Work

  • Honest Processes Only: The current framework is restricted to "honest" diffusions—those that do not lose mass (i.e., the process doesn't "die" or exit the state space entirely).
  • Regularity Constraints: The proofs require specific regularity conditions on the diffusions to ensure measurability and continuity.
  • Future Directions: The authors suggest extending this work to non-honest processes (where mass can be lost) and exploring other types of continuous stochastic processes, such as Lévy processes, which can include jumps alongside continuous flow. They also leave open the question of whether the inequality $\delta^c \leq d^c$ is always strict or if they are equal under certain conditions.

Summary updated

BibTeX
@misc{chen2023behavioural,
  author = {Linan Chen and Florence Clerc and Prakash Panangaden},
  title = {{Behavioural pseudometrics for continuous-time diffusions}},
  year = {2023},
  eprint = {2312.16729},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.16729},
}
Figure