Optimal coadapted coupling for a random walk on the hyper-complete graph

DOI10.1239/JAP/1389370103MaRDI QIDQ5407032zbMATH OpenOpenAlexFDO

Authors Stephen B. Connor

Publication date 4 April 2014

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.2038, https://projecteuclid.org/euclid.jap/1389370103

zbMATH Keywords

cutoff phenomenonoptimal coadapted couplingrandom walk on a groupstochastic control

Mathematics Subject Classification ID

Continuous-time Markov processes on discrete state spaces (60J27) Optimal stochastic control (93E20)

Abstract: The problem of constructing an optimal co-adapted coupling for a pair of symmetric random walks on $Z_2^d$ was considered by Connor and Jacka (2008), and the existence of a coupling which is stochastically fastest in the class of all such co-adapted couplings was demonstrated. In this paper we show how to generalise this construction to an optimal co-adapted coupling for the continuous-time symmetric random walk on $K_n^d$, where $K_n$ is the complete graph with $n$ vertices. Moreover, we show that although this coupling is not maximal for any $n$ (i.e. it does not achieve equality in the coupling inequality), it does tend to a maximal coupling as $noinfty$.

Recommendations

• Optimal Co-Adapted Coupling for the Symmetric Random Walk on the Hypercube
• Fastest Coupling of Random Walks
• Avoidance coupling
• An upper bound on the size of avoidance couplings
• Avoidance couplings on non‐complete graphs

Cites work

• A Gibbs sampler on the \(n\)-simplex
• A maximal coupling for Markov chains
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Characterization of maximal Markovian couplings for diffusion processes
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 3720745 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 6944 (Why is no real title available?)
• scientific article; zbMATH DE number 1834589 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3035137 (Why is no real title available?)
• Maximal coupling of Euclidean Brownian motions
• Mixing Rates for a Random Walk on the Cube
• On uniqueness of maximal coupling for diffusion processes with a reflection
• Optimal Co-Adapted Coupling for the Symmetric Random Walk on the Hypercube
• The cutoff phenomenon in finite Markov chains.

Cited in

(9)

• Coupling, local times, immersions
• Max-min fair rate allocation and routing in energy harvesting networks: algorithmic analysis
• Optimal Co-Adapted Coupling for the Symmetric Random Walk on the Hypercube
• Fastest Coupling of Random Walks
• An upper bound on the size of avoidance couplings
• Monotonicity of avoidance coupling on \(K_N\)
• Optimal coupling of jumpy Brownian motion on the circle
• Optimal Markovian coupling for finite activity Lévy processes
• Avoidance coupling

This page was built for publication: Optimal coadapted coupling for a random walk on the hyper-complete graph

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