Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-07T00:46:17.747Z Has data issue: false hasContentIssue false
  • English
  • Français

An Upper Bound on the Size of Avoidance Couplings

Part of: Markov processes Graph theory

Published online by Cambridge University Press:  11 December 2018

ERIK BATES  and
LISA SAUERMANN
ERIK BATES
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: ewbates@stanford.edu, lsauerma@stanford.edu)
LISA SAUERMANN
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: ewbates@stanford.edu, lsauerma@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.

We show that a coupling of non-colliding simple random walkers on the complete graph on n vertices can include at most n - log n walkers. This improves the only previously known upper bound of n - 2 due to Angel, Holroyd, Martin, Wilson and Winkler (Electron. Commun. Probab.18 (2013)). The proof considers couplings of i.i.d. sequences of Bernoulli random variables satisfying a similar avoidance property, for which there is separate interest.

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 05C81: Random walks on graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 3 , May 2019 , pp. 325 - 334
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

†

Research was partially supported by NSF grant DGE-114747.

References

[1] Angel, O., Holroyd, A. E., Martin, J., Wilson, D. B. and Winkler, P. (2013) Avoidance coupling. Electron. Commun. Probab. 18 58.Google Scholar
[2] Balister, P. N., Bollobás, B. and Stacey, A. M. (2000) Dependent percolation in two dimensions. Probab. Theory Rel. Fields 117 495–513.Google Scholar
[3] Basu, R., Sidoravicius, V. and Sly, A. (2014) Scheduling of non-colliding random walks. arXiv:1411.4041Google Scholar
[4] Benjamini, I., Burdzy, K. and Chen, Z.-Q. (2007) Shy couplings. Probab. Theory Rel. Fields 137 345–377.Google Scholar
[5] Bramson, M., Burdzy, K. and Kendall, W. (2013) Shy couplings, CAT(0) spaces, and the Lion and Man. Ann. Probab. 41 744–784.Google Scholar
[6] Bramson, M., Burdzy, K. and Kendall, W. S. (2014) Rubber bands, pursuit games and shy couplings. Proc. Lond. Math. Soc. (3) 109 121–160.Google Scholar
[7] Coppersmith, D., Tetali, P. and Winkler, P. (1993) Collisions among random walks on a graph. SIAM J. Discrete Math. 6 363–374.Google Scholar
[8] Feldheim, O. N. (2017) Monotonicity of avoidance coupling on KN. Combin. Probab. Comput. 26 16–23.Google Scholar
[9] Gács, P. (2011) Clairvoyant scheduling of random walks. Random Struct. Alg. 39 413–485.Google Scholar
[10] Infeld, E. J. (2016) Uniform avoidance coupling, design of anonymity systems and matching theory. PhD thesis, Dartmouth College.Google Scholar
[11] Kendall, W. S. (2009) Brownian couplings, convexity, and shy-ness. Electron. Commun. Probab. 14 66–80.Google Scholar
[12] 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
[13] Tsianos, K. I. (2013) The role of the network in distributed optimization algorithms: Convergence rates, scalability, communication/computation tradeoffs and communication delays. PhD thesis, McGill University.Google Scholar
[14] Winkler, P. (2000) Dependent percolation and colliding random walks. Random Struct. Alg. 16 58–84.Google Scholar