Mean field conditions for coalescing random walks

DOI10.1214/12-AOP813zbMATH Open1285.60094arXiv1109.5684OpenAlexW3103640397MaRDI QIDQ378808FDOQ378808

Authors: Roberto I. Oliveira 

Publication date: 12 November 2013

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: The main results in this paper are about the full coalescence time $mathsfC$ of a system of coalescing random walks over a finite graph $G$. Letting $mathsfm(G)$ denote the mean meeting time of two such walkers, we give sufficient conditions under which $mathbfE[mathsfC]approx2mathsfm(G)$ and $mathsfC/mathsfm(G)$ has approximately the same law as in the "mean field" setting of a large complete graph. One of our theorems is that mean field behavior occurs over all vertex-transitive graphs whose mixing times are much smaller than $mathsfm(G)$; this nearly solves an open problem of Aldous and Fill and also generalizes results of Cox for discrete tori in $dgeq2$ dimensions. Other results apply to nonreversible walks and also generalize previous theorems of Durrett and Cooper et al. Slight extensions of these results apply to voter model consensus times, which are related to coalescing random walks via duality. Our main proof ideas are a strengthening of the usual approximation of hitting times by exponential random variables, which give results for nonstationary initial states; and a new general set of conditions under which we can prove that the hitting time of a union of sets behaves like a minimum of independent exponentials. In particular, this will show that the first meeting time among $k$ random walkers has mean $$.

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

Recommendations

• On the coalescence time of reversible random walks
• From coalescing random walks on a torus to Kingman's coalescent
• On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
• Coalescent random walks on graphs
• Mean field behavior during the big bang regime for coalescing random walks

zbMATH Keywords

hitting timesvoter modelcoalescing random walksexponential approximation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random graph dynamics
• Title not available (Why is that?)
• Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
• Inequalities for rare events in time-reversible Markov chains. II
• Multiple random walks in random regular graphs
• On the coalescence time of reversible random walks
• A note on percolation on \(\mathbb Z^d\): isoperimetric profile via exponential cluster repulsion
• On the mixing time of a simple random walk on the super critical percolation cluster
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Markov chains with almost exponential hitting times
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph

Cited In (24)

• Voter models on subcritical scale‐free random graphs
• Discordant edges for the voter model on regular random graphs
• On the meeting of random walks on random DFA
• Conditioned, quasi-stationary, restricted measures and escape from metastable states
• Uniformity of the late points of random walk on \({\mathbb {Z}}_{n}^{d}\) for \(d \geq 3\)
• Metastability for general dynamics with rare transitions: escape time and critical configurations
• Latent voter model on locally tree-like random graphs
• Coalescence and meeting times on \(n\)-block Markov chains
• Wright-Fisher diffusions in stochastic spatial evolutionary games with death-birth updating
• Weak atomic convergence of finite voter models toward Fleming-Viot processes
• Broadcasting on paths and cycles
• Meeting, coalescence and consensus time on random directed graphs
• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• On broadcasting time in the model of travelling agents
• Hitting times of rare events in Markov chains
• Coalescing random walk on unimodular graphs
• Metastable Markov chains
• From coalescing random walks on a torus to Kingman's coalescent
• Discursive voter models on the supercritical scale-free network
• Precise asymptotics of some meeting times arising from the voter model on large random regular graphs
• Discordant voting protocols for cyclically linked agents
• Mean field behavior during the big bang regime for coalescing random walks
• Some inequalities for reversible Markov chains and branching random walks via spectral optimization
• Voting protocols on the star graph

This page was built for publication: Mean field conditions for coalescing random walks

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