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)

Request Permissions   Purchase Content 


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

  • 1. David J. Aldous, Meeting times for independent Markov chains, Stochastic Process. Appl. 38 (1991), no. 2, 185–193. MR 1119980, 10.1016/0304-4149(91)90090-Y
  • 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 H. Spencer, The probabilistic method, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000. With an appendix on the life and work of Paul Erdős. MR 1885388
  • 4. J. T. Cox, Coalescing random walks and voter model consensus times on the torus in 𝑍^{𝑑}, Ann. Probab. 17 (1989), no. 4, 1333–1366. MR 1048930
  • 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, 10.1137/S0097539704445226
  • 6. Thomas M. Liggett, Interacting particle systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231

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.