Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T19:25:45.092Z Has data issue: false hasContentIssue false
  • English
  • Français

Monotonicity of Avoidance Coupling on KN

Part of: Markov processes

Published online by Cambridge University Press:  03 June 2016

OHAD N. FELDHEIM
OHAD N. FELDHEIM*
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: ohadfeld@stanford.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Answering a question by Angel, Holroyd, Martin, Wilson and Winkler [1], we show that the maximal number of non-colliding coupled simple random walks on the complete graph KN, which take turns, moving one at a time, is monotone in N. We use this fact to couple [N/4] such walks on KN, improving the previous Ω(N/log N) lower bound of Angel et al. We also introduce a new generalization of simple avoidance coupling which we call partially ordered simple avoidance coupling, and provide a monotonicity result for this extension as well.

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 1 , January 2017 , pp. 16 - 23
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Angel, O., Holroyd, A., Martin, J., Wilson, D. and Winkler, P. (2013) Avoidance coupling. Electron. Commun. Probab. 18 1–13.Google Scholar
[2] Benjamini, I., Burdzy, K. and Chen, Z. (2007) Shy couplings. Probab. Theory Rel. Fields 137 345–377.Google Scholar
[3] Bramson, M., Burdzy, K. and Kendall, W. (2010) Shy couplings, CAT(0) spaces, and the lion and man. Ann. Probab. 41 744–784.Google Scholar
[4] Coppersmith, D., Tetali, P. and Winkler, P. (1993) Collisions among random walks on a graph. SIAM J. Discrete Math. 6 363–374.Google Scholar
[5] Gács, P. (2011) Clairvoyant scheduling of random walks. Random Struct. Alg. 39 413–485.Google Scholar
[6] Kendall, W. (2009) Brownian couplings, convexity, and shy-ness. Electron. Commun. Probab. 14 66–80.CrossRefGoogle Scholar
[7] Tetali, P. and Winkler, P. (1993) Simultaneous reversible Markov chains. In Combinatorics: Paul Erdős is Eighty, Vol. 1, János Bolyai Mathematical Society, pp. 433–451.Google Scholar