License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.18
URN: urn:nbn:de:0030-drops-64335
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6433/
Go to the corresponding LIPIcs Volume Portal

Betz, Volker ; Le Roux, Stéphane

Stable States of Perturbed Markov Chains

pdf-format:
LIPIcs-MFCS-2016-18.pdf (0.5 MB)

Abstract

Given an infinitesimal perturbation of a discrete-time finite Markov chain, we seek the states that are stable despite the perturbation, i.e. the states whose weights in the stationary distributions can be bounded away from 0 as the noise fades away. Chemists, economists, and computer scientists have been studying irreducible perturbations built with monomial maps. Under these assumptions, Young proved the existence of and computed the stable states in cubic time. We fully drop these assumptions, generalize Young's technique, and show that stability is decidable as long as f in O(g) is. Furthermore, if the perturbation maps (and their multiplications) satisfy f in O(g) or g in O(f), we prove the existence of and compute the stable states and the metastable dynamics at all time scales where some states vanish. Conversely, if the big-O assumption does not hold, we build a perturbation with these maps and no stable state. Our algorithm also runs in cubic time despite the weak assumptions and the additional work. Proving its correctness relies on new or rephrased results in Markov chain theory, and on algebraic abstractions thereof.

BibTeX - Entry

@InProceedings{betz_et_al:LIPIcs:2016:6433,
  author =	{Volker Betz and St{\'e}phane Le Roux},
  title =	{{Stable States of Perturbed Markov Chains}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6433},
  URN =		{urn:nbn:de:0030-drops-64335},
  doi =		{10.4230/LIPIcs.MFCS.2016.18},
  annote =	{Keywords: evolution, metastability, tropical, shortest path, SCC, cubic time}
}

Keywords: evolution, metastability, tropical, shortest path, SCC, cubic time
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI