Random walks colliding before getting trapped

DOI10.1214/16-EJP4414MaRDI QIDQ303555zbMATHOpenAlexFDO

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)

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

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)

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$.

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

Cited in

(3)

• Asymptotic behaviour of the noisy voter model density process
• scientific article; zbMATH DE number 5896696 (Why is no real title available?)
• Collisions of several walkers in recurrent random environments

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)