Asymptotic behavior of strongly interacting Markov chains
Abstract
ASYMPTOTIC BEHAVIOR OF STRONGLY INTERACTING MARKOV CHAINS Systems of interacting stochastically evolving particles model diverse phenomena such as distributed computing, the spread of diseases, consensus formation, and neuronal networks. In many models, the infinitesimal evolution of the state of a particle only depends on its current state and the current distribution of the states of neighboring particles, as specified by an underlying interaction graph. Key measures of system performance include various functionals of the empirical distribution (which captures the fractions of particles in different states), as well as the dynamics of a typical particle in the system. Examples of questions that one would like to answer for such systems are which distributed algorithms perform well? What fraction of time is a site infected in a finite interval? What leads to oscillations and synchronous behavior in the brain? However, the design and performance analysis of these systems is extremely challenging from a mathematical point of view. The number of interacting particles is typically large, making rigorous analysis of their properties particularly challenging, and numerical simulation either infeasible or not sufficiently insightful. The analysis is further complicated when the underlying graph is itself random, which is relevant for many applications where connections between particles may be intermittent or their precise structure unknown. As a result, one often seeks tractable approximations that can be proved to be accurate in a suitable asymptotic regime. Previous work has mostly focused on dense interaction graphs, when each particle has a large number of neighbors. In this case the topology of the graph becomes irrelevant and so-called mean-field limits serve as reasonable approximations for large systems. In contrast, these questions are poorly understood in the sparse case, where each particle interacts only with a uniformly bounded (average) number of neighbors, and the topology of the interacting graph plays a role. This proposal aims to develop a completely novel mathematical framework for the study of large collections of both discrete-time and continuous-time interacting jump stochastic processes governed by sparse interaction graphs. Specific goals include: (i) Identification of sequences of sparse interaction graphs whose sizes increase to infinity for which one can establish convergence of the corresponding dynamics to a limit process. (ii) Finding sufficient conditions under which the corresponding sequence of global empirical distributions converges to a limit and obtaining a useful characterization of the limit. (iii) Obtaining an autonomous description of the dynamics of a typical particle and developing both computational and analytical tools for the study of these dynamics. (iv) Development of efficient computational algorithms for simulation of local dynamics. (v) Study of multitype, heterogeneous systems with directed interaction graphs. (vi) Application of the analytical and computational framework developed to study and gain insight into numerous concrete models of interest. The work will combine tools from random graph theory, Markov random fields and stochastic analysis, and involve the training of two graduate students. The proposed work is to develop technology for both military and civil applications. PUBLICLY RELEASABLE.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 09, 2020
- Source ID
- W911NF2010133
Entities
People
- Kavita Ramanan
Organizations
- Army Contracting Command
- Brown University
- United States Army