Intersection and mixing times for reversible chains
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
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
Journal Title
Conference Name
Journal ISSN
1083-6489