An upper bound on the size of avoidance couplings

DOI10.1017/S0963548318000500zbMATH Open1434.60180arXiv1712.00210MaRDI QIDQ5222540FDOQ5222540

Authors: Erik Bates, Lisa Sauermann 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: We show that a coupling of non-colliding simple random walkers on the complete graph on $n$ vertices can include at most $n-logn$ walkers. This improves the only previously known upper bound of $n-2$ due to Angel, Holroyd, Martin, Wilson, and Winkler ({it 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. Our bound in this setting should be closer to optimal.

Full work available at URL: https://arxiv.org/abs/1712.00210

Recommendations

• Monotonicity of avoidance coupling on \(K_N\)
• Avoidance coupling
• Avoidance couplings on non‐complete graphs
• scientific article; zbMATH DE number 19362
• Optimal coadapted coupling for a random walk on the hyper-complete graph

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Cites Work

• Shy couplings, \(\mathrm{CAT}(0)\) spaces, and the lion and man
• Collisions Among Random Walks on a Graph
• Dependent percolation in two dimensions
• Clairvoyant scheduling of random walks
• Title not available (Why is that?)
• Rubber bands, pursuit games and shy couplings
• Scheduling of Non-Colliding Random Walks

Cited In (1)

• Avoidance couplings on non‐complete graphs

This page was built for publication: An upper bound on the size of avoidance couplings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222540)