Intersection and mixing times for reversible chains

DOI10.1214/16-EJP18zbMATH Open1357.60076arXiv1412.8458WikidataQ105584311 ScholiaQ105584311MaRDI QIDQ508469FDOQ508469

Authors: Yuval Peres, Thomas Sauerwald, Perla Sousi, Alexandre Stauffer 

Publication date: 7 February 2017

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

Abstract: Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.

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

Recommendations

• Mixing times are hitting times of large sets
• Mixing and hitting times for finite Markov chains
• Meeting times for independent Markov chains
• scientific article; zbMATH DE number 1195779
• Mixing times and moving targets

zbMATH Keywords

random walkmartingalemixing timereversible Markov chainsDoob's maximal inequalityintersection time

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50)

Cited In (9)

• Voter models on subcritical scale‐free random graphs
• Coalescence and meeting times on \(n\)-block Markov chains
• On the coalescence time of reversible random walks
• Random walks colliding before getting trapped
• Intersection conductance and canonical alternating paths: methods for general finite Markov chains
• Estimating graph parameters with random walks
• Mixing times are hitting times of large sets
• Elementary bounds on mixing times for decomposable Markov chains
• Some inequalities for reversible Markov chains and branching random walks via spectral optimization

This page was built for publication: Intersection and mixing times for reversible chains

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