Random walks colliding before getting trapped

DOI10.1214/16-EJP4414zbMATH Open1345.60084arXiv1506.07845OpenAlexW2963881281MaRDI QIDQ303555FDOQ303555

Authors: Louigi Addario-Berry, Yuval Peres, Perla Sousi, Roberto I. Oliveira 

Publication date: 22 August 2016

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: Let $P$ be the transition matrix of a finite, irreducible and reversible Markov chain. We say the continuous time Markov chain $X$ has transition matrix $P$ and speed $lambda$ if it jumps at rate $lambda$ according to the matrix $P$. Fix $lambd{a}_X,lambd{a}_Y,lambd{a}_{Z}geq0$, then let $X,Y$ and $Z$ be independent Markov chains with transition matrix $P$ and speeds $lambd{a}_X,lambd{a}_Y$ and $lambd{a}_Z$ respectively, all started from the stationary distribution. What is the chance that $X$ and $Y$ meet before either of them collides with $Z$? For each choice of $lambd{a}_X,lambd{a}_Y$ and $lambd{a}_Z$ with $max(lambd{a}_X,lambd{a}_Y)>0$, we prove a lower bound for this probability which is uniform over all transitive, irreducible and reversible chains. In the case that $lambd{a}_X=lambd{a}_Y=1$ and $lambd{a}_Z=0$ we prove a strengthening of our main theorem using a martingale argument. We provide an example showing the transitivity assumption cannot be removed for general $lambd{a}_X,lambd{a}_Y$ and $lambd{a}_Z$.

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

Recommendations

• Meeting times for independent Markov chains
• Surprise probabilities in Markov chains
• scientific article; zbMATH DE number 524141
• Fastest Mixing Markov Chain on a Path
• Intersection and mixing times for reversible chains

zbMATH Keywords

continuous-time Markov chainmartingalehitting timesrandom walksmixing timemeeting times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Continuous-time Markov processes on discrete state spaces (60J27)

Cited In (3)

• Asymptotic behaviour of the noisy voter model density process
• Collisions of several walkers in recurrent random environments
• Title not available (Why is that?)

This page was built for publication: Random walks colliding before getting trapped

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