On the metric-based approximate minimization of Markov chains

Bacci, Giovanni and Bacci, Giorgio and Larsen, Kim G. and Mardare, Radu; Muscholl, Anca and Indyk, Piotr and Kuhn, Fabian and Chatzigiannakis, Ioannis, eds. (2017) On the metric-based approximate minimization of Markov chains. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, POL. ISBN 9783959770415 (https://doi.org/10.4230/LIPIcs.ICALP.2017.104)

[thumbnail of Bacci-etal-ICALP2017-On-metric-based-approximate-minimization-Markov-chains]
Preview
 Text. Filename: Bacci_etal_ICALP2017_On_metric_based_approximate_minimization_Markov_chains.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (620kB)| Preview

Abstract

We address the behavioral metric-based approximate minimization problem of Markov Chains (MCs), i.e., given a finite MC and a positive integer k, we are interested in finding a k-state MC of minimal distance to the original. By considering as metric the bisimilarity distance of Desharnais at al., we show that optimal approximations always exist; show that the problem can be solved as a bilinear program; and prove that its threshold problem is in PSPACE and NP-hard. Finally, we present an approach inspired by expectation maximization techniques that provides suboptimal solutions. Experiments suggest that our method gives a practical approach that outperforms the bilinear program implementation run on state-of-the-art bilinear solvers.

CORE (COnnecting REpositories)