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.ITCS.2018.58
URN: urn:nbn:de:0030-drops-83317
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8331/
Go to the corresponding LIPIcs Volume Portal

Chazelle, Bernard

Toward a Theory of Markov Influence Systems and their Renormalization

pdf-format:
LIPIcs-ITCS-2018-58.pdf (1 MB)

Abstract

Nonlinear Markov chains are probabilistic models commonly used in physics, biology, and the social sciences. In "Markov influence systems" (MIS), the transition probabilities of the chains change as a function of the current state distribution. This work introduces a renormalization framework for analyzing the dynamics of MIS. It comes in two independent parts: first, we generalize the standard classification of Markov chain states to the dynamic case by showing how to "parse" graph sequences. We then use this framework to
carry out the bifurcation analysis of a few important MIS families.
In particular, we show that irreducible MIS are almost always
asymptotically periodic. We also give an example of "hyper-torpid" mixing, where a stationary distribution is reached in super-exponential time, a timescale that cannot be achieved by any Markov chain.

BibTeX - Entry

@InProceedings{chazelle:LIPIcs:2018:8331,
  author =	{Bernard Chazelle},
  title =	{{Toward a Theory of Markov Influence Systems and their Renormalization}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8331},
  URN =		{urn:nbn:de:0030-drops-83317},
  doi =		{10.4230/LIPIcs.ITCS.2018.58},
  annote =	{Keywords: Markov influence systems, nonlinear Markov chains, dynamical systems, renormalization, graph sequence parsing}
}

Keywords: Markov influence systems, nonlinear Markov chains, dynamical systems, renormalization, graph sequence parsing
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

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