2018/02/04 by Chazelle, Bernard
#Adaptation and Self-Organizing Systems (nlin.AO) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Multiagent Systems (cs.MA) #Probability (math.PR)
paper · doi:10.48550/arxiv.1802.01208
We introduce the concept of a Markov influence system (MIS) and analyze its dynamics. An MIS models a random walk in a graph whose edges and transition probabilities change endogenously as a function of the current distribution. This article consists of two independent parts: in the first one, we generalize the standard classification of Markov chain states to the time-varying case by showing how to "parse" graph sequences; in the second part, we use this framework to carry out the bifurcation analysis of a few important MIS families. We show that, in general, these systems can be chaotic but that irreducible MIS are almost always asymptotically periodic. We give an example of "hyper-torpid" mixing, where a stationary distribution is reached in super-exponential time, a timescale beyond the reach of any Markov chain.