Document Open Access Logo

Toward a Theory of Markov Influence Systems and their Renormalization

Author Bernard Chazelle

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.58.pdf
  • Filesize: 1.08 MB
  • 18 pages

Document Identifiers

Author Details

Bernard Chazelle

Cite As Get BibTex

Bernard Chazelle. Toward a Theory of Markov Influence Systems and their Renormalization. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.58

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.

Subject Classification

Keywords
  • Markov influence systems
  • nonlinear Markov chains
  • dynamical systems
  • renormalization
  • graph sequence parsing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. C. Avin, M. Koucký, and Z. Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). Proc. 35th ICALP, pages 121-132, 2008. Google Scholar
  2. H. Bruin and J.H.B. Deane. Piecewise contractions are asymptotically periodic. Proc. American Mathematical Society, 137(4):1389-1395, 2009. Google Scholar
  3. C. Castellano, S. Fortunato, and V. Loreto. Statistical physics of social dynamics. Rev. Mod. Phys., 81:591-646, 2009. Google Scholar
  4. B. Chazelle. Diffusive influence systems. SIAM J. Comput., 44:1403-1442, 2015. Google Scholar
  5. B. Chazelle, Q. Jiu, Q. Li, and C. Wang. Well-posedness of the limiting equation of a noisy consensus model in opinion dynamics. J. Differential Equations, 263:365-397, 2017. Google Scholar
  6. A. Condon and D. Hernek. Random walks on colored graphs. Random Structures and Algorithms, 5:285-303, 1994. Google Scholar
  7. A. Condon and R.J. Lipton. On the complexity of space bounded interactive proofs. Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 462-267, 1989. Google Scholar
  8. D. Coppersmith and P. Diaconis. Random walk with reinforcement. Unpublished manuscript, 1986. Google Scholar
  9. O. Denysyuk and L. Rodrigues. Random walks on directed dynamic graphs. Proc. 2nd International Workshop on Dynamic Networks: Algorithms and Security (DYNAS'10), Bordeaux, France (Also arXiv:1101.5944 (2011)), 2010. Google Scholar
  10. O. Denysyuk and L. Rodrigues. Random walks on evolving graphs with recurring topologies. Proc. 28th International Symposium on Distributed Computing (DISC), 2014. Google Scholar
  11. R.L. Devaney. An Introduction to Chaotic Dynamical Systems (2nd ed.). Westview Press, 2003. Google Scholar
  12. P. Diaconis. Recent progress on de Finetti’s notions of exchangeability. Bayesian Statistics, 3, 1988. Google Scholar
  13. T.D. Frank. Strongly nonlinear stochastic processes in physics and the life sciences. ISRN Mathematical Physics, Article ID 149169, 2013. Google Scholar
  14. P. Holme and J. Saramäki. Temporal networks. Physics Reports, 519:97-125, 2012. Google Scholar
  15. G. Iacobelli and D.R. Figueiredo. Edge-attractor random walks on dynamic networks. J. Complex Networks, 5:84-110, 2017. Google Scholar
  16. A. Katok and B. Hasselblatt. Introduction to the Modern Theory of Dynamical Systems. Cambridge University Press, 1996. Google Scholar
  17. D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. J. Computer and System Sciences, 64:820-842, 2002. Google Scholar
  18. V.N. Kolokoltsov. Nonlinear Markov Processes and Kinetic Equations. Cambridge Tracks in Mathematics (182), Cambridge Univ. Press, 2010. Google Scholar
  19. M. Othon. An introduction to temporal graphs: an algorithmic perspective. Internet Mathematics, 12, 2016. Google Scholar
  20. E. Seneta. Non-Negative Matrices and Markov Chains. Springer, 2nd ed., 2006. Google Scholar
  21. S. Sternberg. Dynamical Systems. Dover Books on Mathematics, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact