Approximation Metrics Based on Probabilistic Bisimulations for General State-Space Markov Processes: A Survey

This article provides a survey of approximation metrics for stochastic processes. We deal with Markovian processes in discrete time evolving on general state spaces, namely on domains with infinite cardinality and endowed with proper measurability and metric structures. The focus of this work is to discuss approximation metrics between two such processes, based on the notion of probabilistic bisimulation: in particular we investigate metrics characterized by an approximate variant of this notion. We suggest that metrics between two processes can be introduced essentially in two distinct ways: the first employs the probabilistic conditional kernels underlying the two stochastic processes under study, and leverages notions derived from algebra, logic, or category theory; whereas the second looks at distances between trajectories of the two processes, and is based on the dynamical properties of the two processes (either their syntax, via the notion of bisimulation function; or their semantics, via sampling techniques). The survey moreover covers the problem of constructing formal approximations of stochastic processes according to the introduced metrics.