Jonathan Hermon

Let (Xₜ )ₜ∈?₊ be an irreducible, aperiodic, reversible Markov chain on a finite state space Ω. LetM := ?mix/?L, where ?mix and ?L are the total variation mixing times of the chain and its lazyversion, respectively. We show - in a precise quantitative sense - that if M is sufficiently large,then the chain is ”near-bipartite”. That is, there exists a bipartition (A, B) of Ω such that π(A)and π(B) are both close to 1/2, and the Markov chain rarely spends two consecutive time stepswithin the same set of the bipartition. In particular, we show that for ? ≫ ?L, the distribution ofXₜ is very close to a mixture of πᴀ and πᴃ.

View record