Toward a theory of markov influence systems and their renormalization

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publication9th Innovations in Theoretical Computer Science, ITCS 2018
EditorsAnna R. Karlin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770606
DOIs
StatePublished - Jan 1 2018
Externally publishedYes
Event9th Innovations in Theoretical Computer Science, ITCS 2018 - Cambridge, United States
Duration: Jan 11 2018Jan 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume94
ISSN (Print)1868-8969

Other

Other9th Innovations in Theoretical Computer Science, ITCS 2018
Country/TerritoryUnited States
CityCambridge
Period1/11/181/14/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamical systems
  • Graph sequence parsing
  • Markov influence systems
  • Nonlinear Markov chains
  • Renormalization

Fingerprint

Dive into the research topics of 'Toward a theory of markov influence systems and their renormalization'. Together they form a unique fingerprint.

Cite this