Linear distances between Markov chains
From MaRDI portal
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Abstract: We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results.
Recommendations
- Converging from branching to linear metrics on Markov chains
- Converging from Branching to Linear Metrics on Markov Chains
- On the total variation distance of labelled Markov chains
- On the total variation distance of semi-Markov chains
- Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains
Cited in
(17)- SOS specifications for uniformly continuous operators
- On the metric-based approximate minimization of Markov chains
- The metric linear-time branching-time spectrum on nondeterministic probabilistic processes
- A probabilistic calculus of cyber-physical systems
- Complete axiomatization for the total variation distance of Markov chains
- Logical characterization of branching metrics for nondeterministic probabilistic transition systems
- On resistance distance of Markov chain and its sum rules
- On the relationship between bisimulation and trace equivalence in an approximate probabilistic context
- Trace and testing metrics on nondeterministic probabilistic processes
- Converging from branching to linear metrics on Markov chains
- On the total variation distance of labelled Markov chains
- Compositional weak metrics for group key update
- Markov chain of distances between parked cars
- Satisfiability of quantitative probabilistic CTL: rise to the challenge
- Approximate constrained lumping of polynomial differential equations
- Learning model checking and the kernel trick for signal temporal logic on stochastic processes
- Logical characterization of trace metrics
This page was built for publication: Linear distances between Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608672)
