Repository logo
 

Intersection and mixing times for reversible chains

Published version
Peer-reviewed

Type

Article

Change log

Authors

Peres, Y 
Sauerwald, T 
Sousi, P 
Stauffer, A 

Abstract

© 2017, University of Washington. All rights reserved. We consider two independent Markov chains on the same finite state space, and study their intersection time, which is the first time that the trajectories of the two chains intersect. We denote by tI the expectation of the intersection time, maximized over the starting states of the two chains. We show that, for any reversible and lazy chain, the total variation mixing time is O(tI). When the chain is reversible and transitive, we give an expression for tI using the eigenvalues of the transition matrix. In this case, we also show that tI is of order √nE[I], where I is the number of intersections of the trajectories of the two chains up to the uniform mixing time, and n is the number of states. For random walks on trees, we show that tI and the total variation mixing time are of the same order. Finally, for random walks on regular expanders, we show that tI is of order √n.

Description

Keywords

intersection time, random walk, mixing time, martingale, Doob's maximal inequality

Journal Title

Electronic Journal of Probability

Conference Name

Journal ISSN

1083-6489
1083-6489

Volume Title

22

Publisher

Institute of Mathematical Statistics