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 Free Access

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?)

  • 1. David Aldous, Meeting times for independent Markov chains, Stochastic Processes and their Applications 38 (1991), 185-193. MR 1119980 (93m:60142)
  • 2. David Aldous and James Allen Fill, Reversible Markov Chains and Random Walks on Graphs, book draft,˜aldous/RWG/book.html.
  • 3. Noga Alon and Joel Spencer, The Probabilistic Method, second ed., Wiley-Interscience Series in Discrete Mathematics, John Wiley and Sons, New York, 2000. MR 1885388 (2003f:60003)
  • 4. J. Theodore Cox, Coalescing random walks and voter model consensus times on the torus in $ {Z}^d$, Annals of Probability 17 (1989), 1333-1366. MR 1048930 (91d:60250)
  • 5. Julia Kempe, Alexei Kitaev, and Oded Regev, The complexity of the local Hamiltonian problem, SIAM J. Comput. 35 (2006), no. 5, 1070-1097. MR 2217138 (2006m:68037)
  • 6. Thomas M. Liggett, Interacting Particle Systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, 1985. MR 776231 (86e:60089)

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