An upper bound on the size of avoidance couplings

DOI10.1017/S0963548318000500MaRDI QIDQ5222540zbMATH OpenFDO

Authors Erik Bates, Lisa Sauermann

Publication date 6 April 2020

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• Clairvoyant scheduling of random walks
• Collisions Among Random Walks on a Graph
• Dependent percolation in two dimensions
• scientific article; zbMATH DE number 524141 (Why is no real title available?)
• Rubber bands, pursuit games and shy couplings
• Scheduling of non-colliding random walks
• Shy couplings, \(\mathrm{CAT}(0)\) spaces, and the lion and man

Cited in

(4)

• Monotonicity of avoidance coupling on \(K_N\)
• Optimal coadapted coupling for a random walk on the hyper-complete graph
• Avoidance couplings on non‐complete graphs
• Avoidance coupling

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)