Monotonicity of avoidance coupling on K_N

DOI10.1017/S0963548316000195MaRDI QIDQ5366931zbMATH OpenFDO

Authors Ohad Noy Feldheim

Publication date 10 October 2017

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

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

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Answering a question by Angel, Holroyd, Martin, Wilson and Winkler, we show that the maximal number of non-colliding coupled simple random walks on the complete graph $K_N$, which take turns, moving one at a time, is monotone in $N$. We use this fact to couple $lceilfracN4ceil$ such walks on $K_N$, improving the previous $Omega(N/logN)$ 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.

Recommendations

• An upper bound on the size of avoidance couplings
• Avoidance coupling
• Avoidance couplings on non‐complete graphs
• Clairvoyant scheduling of random walks
• Optimal coadapted coupling for a random walk on the hyper-complete graph

Cites work

• Avoidance coupling
• Brownian couplings, convexity, and shyness
• Clairvoyant scheduling of random walks
• Collisions Among Random Walks on a Graph
• Shy couplings
• Shy couplings, \(\mathrm{CAT}(0)\) spaces, and the lion and man

Cited in

(4)

• Invariant monotone coupling need not exist
• An upper bound on the size of avoidance couplings
• Avoidance couplings on non‐complete graphs
• Avoidance coupling

This page was built for publication: Monotonicity of avoidance coupling on \(K_N\)

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