Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



On the coalescence time of reversible random walks

Author: Roberto Imbuzeiro Oliveira
Journal: Trans. Amer. Math. Soc. 364 (2012), 2109-2128
MSC (2010): Primary 60J27, 60K35; Secondary 60C05
Published electronically: November 9, 2011
MathSciNet review: 2869200
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Consider a system of coalescing random walks where each individual performs a random walk over a finite graph $ \mathbf {G}$ or (more generally) evolves according to some reversible Markov chain generator $ Q$. Let $ C$ be the first time at which all walkers have coalesced into a single cluster. $ C$ is closely related to the consensus time of the voter model for this $ \mathbf {G}$ or $ Q$.

We prove that the expected value of $ C$ is at most a constant multiple of the largest hitting time of an element in the state space. This solves a problem posed by Aldous and Fill and gives sharp bounds in many examples, including all vertex-transitive graphs. We also obtain results on the expected time until only $ k\geq 2$ clusters remain. Our proof tools include a new exponential inequality for the meeting time of a reversible Markov chain and a deterministic trajectory, which we believe to be of independent interest.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60J27, 60K35, 60C05

Retrieve articles in all journals with MSC (2010): 60J27, 60K35, 60C05

Additional Information

Roberto Imbuzeiro Oliveira
Affiliation: Departamento de Matemática, Instituto Nacaional de Matemática Pura e Aplicada, Rio de Janeiro, RJ, Brazil 22430-040

Keywords: Coalescing random walks, voter model, hitting time
Received by editor(s): September 3, 2010
Received by editor(s) in revised form: September 9, 2010
Published electronically: November 9, 2011
Additional Notes: The author’s work was supported by Bolsa de Produtividade em Pesquisa and by a Pronex grant from CNPq, Brazil.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society