Robust Probabilistic Bisimilarity for Labelled Markov Chains

[FKPB25] Syyeda Zainab Fatmi, Stefan Kiefer, David Parker and Franck van Breugel. Robust Probabilistic Bisimilarity for Labelled Markov Chains. In Proc. 37th International Conference on Computer Aided Verification (CAV'25), volume 15932 of LNCS, pages 254-275, Springer. Distinguished Paper Award. July 2025. pdf bib [Proposes a notion of robust probabilistic bisimulation, and a minimisation algorithm implemented in PRISM.]

Downloads
PDF 783 KBBibTeX
Notes
The original publication is available at link.springer.com.
Search for this paper
Google · Google Scholar

Abstract

Despite its prevalence, probabilistic bisimilarity suffers from a lack of robustness under minuscule perturbations of the transition probabilities. This can lead to discontinuities in the probabilistic bisimilarity distance function, undermining its reliability in practical applications where transition probabilities are often approximations derived from experimental data. Motivated by this limitation, we introduce the notion of robust probabilistic bisimilarity for labelled Markov chains, which ensures the continuity of the probabilistic bisimilarity distance function. We also propose an efficient algorithm for computing robust probabilistic bisimilarity and show that it performs well in practice, as evidenced by our experimental results.