Comparison and analysis of probabilistic systems

17^th February 2023, 13:00 Ashton Lecture Theatre
Qiyi Tang

Abstract

Given a model of computation (e.g., finite automata), and two instances of it, are they semantically equivalent (e.g., do the automata accept the same language)? Such equivalence problems can be viewed as a fundamental question for almost any model of computation. In this talk, we try to answer the fundamental questions for some probabilistic models (Markov chains and Markov decision processes).

We focus on probabilistic bisimilarity, the most prominent notion of behavioural equivalence. We will then have a look at a more robust notion of probabilistic bisimilarity distance, a quantitative generalisation of probabilistic bisimilarity.

We show the following:
* For labelled Markov chains, the development of algorithms to compute probabilistic bisimilarity distance.
* Policy iteration algorithm can be applied to compute the probabilistic bisimilarity distances for labelled Markov chains. In particular, simple policy iteration algorithm takes exponential time in the worst case.
* Comparison of Markov decision processes in terms of probabilistic bisimilarity.