TY - GEN
T1 - Toward a theory of markov influence systems and their renormalization
AU - Chazelle, Bernard
N1 - Publisher Copyright:
© Bernard Chazelle.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - 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.
AB - 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.
KW - Dynamical systems
KW - Graph sequence parsing
KW - Markov influence systems
KW - Nonlinear Markov chains
KW - Renormalization
UR - http://www.scopus.com/inward/record.url?scp=85041691230&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041691230&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2018.58
DO - 10.4230/LIPIcs.ITCS.2018.58
M3 - Conference contribution
AN - SCOPUS:85041691230
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 9th Innovations in Theoretical Computer Science, ITCS 2018
A2 - Karlin, Anna R.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 9th Innovations in Theoretical Computer Science, ITCS 2018
Y2 - 11 January 2018 through 14 January 2018
ER -