Avoidance Coupling

Omer Angel (University of British Columbia)
Alexander E Holroyd (Microsoft Research)
James Martin (University of Oxford)
Peter Winkler (Dartmouth College)
David B Wilson (Microsoft Research)

Abstract


We examine the question of whether a collection of random walks on a graph can be coupled so that they never collide.  In particular, we show that on the complete graph on n vertices, with or without loops, there is a Markovian coupling keeping apart Omega(n/log n) random walks, taking turns to move in discrete time.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-13

Publication Date: July 9, 2013

DOI: 10.1214/ECP.v18-2275

References

  • David Aldous and James Fill. hrefhttp://www.stat.berkeley.edu/~aldous/RWG/book.htmlReversible Markov Chains and Random Walks on Graphs. 2002. Draft, http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  • Benjamini, Itai; Burdzy, Krzysztof; Chen, Zhen-Qing. Shy couplings. Probab. Theory Related Fields 137 (2007), no. 3-4, 345--377. MR2278461
  • Maury Bramson, Krzysztof Burdzy, and Wilfrid~S. Kendall. Shy couplings, CAT(0) spaces, and the lion and man. 2010. arXiv:1007.3199.
  • Coppersmith, Don; Tetali, Prasad; Winkler, Peter. Collisions among random walks on a graph. SIAM J. Discrete Math. 6 (1993), no. 3, 363--374. MR1229691
  • Gács, Peter. Clairvoyant scheduling of random walks. Random Structures Algorithms 39 (2011), no. 4, 413--485. MR2846299
  • Kendall, Wilfrid S. Brownian couplings, convexity, and shy-ness. Electron. Commun. Probab. 14 (2009), 66--80. MR2481667
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937 http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf
  • Tetali, P.; Winkler, P. Simultaneous reversible Markov chains. Combinatorics, Paul Erdős is eighty, Vol. 1, 433--451, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993. MR1249726
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.