Toward a theory of Markov influence systems and their renormalization

DOI10.4230/LIPICS.ITCS.2018.58MaRDI QIDQ4993328zbMATH OpenOpenAlexFDO

Authors Bernard Chazelle

Publication date 15 June 2021

Full work available at URL https://arxiv.org/abs/1802.01208

zbMATH Keywords

dynamical systemsgraph sequence parsingMarkov influence systemsnonlinear Markov chainsrenormalization

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Universality and renormalization of dynamical systems (37E20) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Network design and communication in computer systems (68M10)

Abstract: 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.

Recommendations

• Renormalization group for Markov chains and application to metastability
• Communication, dynamics, and renormalization
• Diffusive influence systems
• scientific article; zbMATH DE number 797405
• On the convergence of nonlinear Markov chains

Cites work

• An introduction to temporal graphs: an algorithmic perspective
• Connectivity and inference problems for temporal networks
• Diffusive influence systems
• Dynamical systems
• Edge-attractor random walks on dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• scientific article; zbMATH DE number 4161783 (Why is no real title available?)
• scientific article; zbMATH DE number 1963551 (Why is no real title available?)
• scientific article; zbMATH DE number 776267 (Why is no real title available?)
• Non-negative matrices and Markov chains.
• Nonlinear Markov processes and kinetic equations.
• Piecewise contractions are asymptotically periodic
• Random walks on colored graphs
• Strongly nonlinear stochastic processes in physics and the life sciences
• Well-posedness of the limiting equation of a noisy consensus model in opinion dynamics

Cited in

(4)

• Self-switching Markov chains: emerging dominance phenomena
• Some observations on dynamic random walks and network renormalization
• Communication, dynamics, and renormalization
• Diffusive influence systems

This page was built for publication: Toward a theory of Markov influence systems and their renormalization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993328)