An official website of the United States government
Consider a system of homogeneous interacting diffusive particles labeled by the nodes of a unimodular Galton–Watson tree, where the state of each node evolves infinitesi- mally like a d-dimensional diffusion whose drift coefficient depends on (the histories of) its own state and the states of neighboring nodes, and whose diffusion coefficient depends only on (the history of) its own state. Under suitable regularity assumptions on the coefficients, an autonomous characterization is obtained for the marginal dis- tribution of the dynamics of the neighborhood of a typical node in terms of a certain local equation, which is a new kind of stochastic differential equation that is nonlinear in the sense of McKean. This equation describes a finite-dimensional non-Markovian stochastic process whose infinitesimal evolution at any time depends not only on the structure and current state of the neighborhood, but also on the conditional law of the current state given the past of the states of neighborhing nodes until that time. Such marginal distributions are of interest because they arise as weak limits of both marginal distributions and empirical measures of interacting diffusions on many sequences of sparse random graphs, including the configuration model and Erdös–Rényi graphs whose average degrees converge to a finite non-zero limit. The results obtained complement classical results in the mean-field regime, which characterize the limiting dynamics of homogeneous interacting diffusions on complete graphs, as the num- ber of nodes goes to infinity, in terms of a corresponding nonlinear Markov process. However, in the sparse graph setting, the topology of the graph strongly influences the dynamics, and the analysis requires a completely different approach. The proofs of existence and uniqueness of the local equation rely on delicate new conditional independence and symmetry properties of particle trajectories on unimodular Galton– Watson trees, as well as judicious use of changes of measure.
more »
« less
Hydrodynamic limits of non-Markovian interacting particle systems on sparse graphs
Consider an interacting particle system indexed by the vertices of a (possibly random) locally finite graph whose vertices and edges are equipped with weights or marks that represent parameters of the model, such as the environment and initial conditions. Each particle takes values in a countable state space and evolves according to a pure jump process whose jump rates depend only on its own state (or history) and marks, and states (or histories) and marks of particles and edges in its neighborhood. Under mild conditions on the jump rates, it is shown that if the sequence of (marked) interaction graphs converges in probability in the local weak sense to a limit (marked) graph that satisfies a certain finite dissociability property, then the corresponding sequence of empirical measures of the particle trajectories converges weakly to the law of the marginal dynamics at the root vertex of the limit graph. The proof of this hydrodynamic limit relies on several auxiliary results of potentially independent interest. First, such interacting particle systems are shown to be well-posed on (almost surely) finitely dissociable graphs, which include graphs with uniformly bounded maximum degrees and any Galton-Watson tree whose offspring distribution has a finite first moment. A counterexample is also provided to show that well-posedness can fail for dynamics on graphs outside this class. Next, given any sequence of graphs that converges in the local weak sense to a finitely dissociable graph, it is shown that the corresponding sequence of jump processes also converges in the same sense to a jump process on the limit graph. Finally, the dynamics are also shown to exhibit an (annealed) asymptotic correlation decay property. These results complement recent work on hydrodynamic limits of locally interacting probabilistic cellular automata and diffusions on sparse random graphs. However, the analysis of jump processes requires very different techniques, including percolation arguments and notions such as consistent spatial localization and causal chains.
more »
« less
- Award ID(s):
- 2246838
- PAR ID:
- 10582270
- Publisher / Repository:
- Institute of Mathematical Statistics
- Date Published:
- Journal Name:
- Electronic Journal of Probability
- Volume:
- 29
- ISSN:
- 1083-6489
- Page Range / eLocation ID:
- 1-63
- Subject(s) / Keyword(s):
- correlation decay empirical measure convergence Galton-Watson process Hydrodynamic limits interacting particle systems Jump processes Local weak limits Poisson random measures Random graphs
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let be a finite, connected graph. We consider a greedy selection of vertices: given a list of vertices , take to be any vertex maximizing the sum of distances to the vertices already chosen and iterate, keep adding the “most remote” vertex. The frequency with which the vertices of the graph appear in this sequence converges to a set of probability measures with nice properties. The support of these measures is, generically, given by a rather small number of vertices . We prove that this suggests that the graphGis, in a suitable sense, “m‐dimensional” by exhibiting an explicit 1‐Lipschitz embedding with good properties.more » « less
-
ter Beek, Maurice; Koutny, Maciej; Rozenberg, Grzegorz (Ed.)For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices.more » « less
-
We consider single-source shortest path algorithms that perform a sequence of relaxation steps whose ordering depends only on the input graph structure and not on its weights or the results of prior steps. Each step examines one edge of the graph, and replaces the tentative distance to the endpoint of the edge by its minimum with the tentative distance to the start of the edge, plus the edge length. As we prove, among such algorithms, the Bellman-Ford algorithm has optimal complexity for dense graphs and near-optimal complexity for sparse graphs, as a function of the number of edges and vertices in the given graph. Our analysis holds both for deterministic algorithms and for randomized algorithms that find shortest path distances with high probability.more » « less
-
Abstract Given a graph of degree over vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth , we develop a local message passing algorithm whose complexity is , and that achieves near optimal cut values among all ‐local algorithms. Focusing on max‐cut, the algorithm constructs a cut of value , where is the value of the Parisi formula from spin glass theory, and (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, that is, graphs whose girth becomes after removing a small fraction of vertices. Earlier work established that, for random ‐regular graphs, the typical max‐cut value is . Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max‐cut, and nearly maximum min‐bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near‐Ramanujan property of random regular graphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1214/24-EJP1243
