We provide new upper bounds for mixing times of general finite Markov chains. We use these bounds to show that the total variation mixing time is robust under rough isometry for bounded degree graphs that are roughly isometric to trees.
Returning to mixing times, Oliveira @cite_7 and independently Peres and Sousi @cite_6 showed that for reversible chains, not only does hold, but in fact @math for any @math . Peres and Sousi then used this equivalence to show that if @math and @math are two lazy reversible Markov chains on the same tree @math with conductances bounded above and below by some strictly positive constants, then Our Theorem yields another simple proof of ): see Corollary . The equivalence @math in the more delicate case @math was later established by @cite_4 .
@cite_4 @cite_6 @cite_7
2128271519 1989183425 1985980054
Given an irreducible discrete time Markov chain on a finite state space, we consider the largest expected hitting time T(α) of a set of stationary measure at least α for α ∈ (0, 1). We obtain tight inequalities among the values of T(α) for different choices of α. One consequence is that T(α) ≤ T(1 2) α for all α < 1 2. As a corollary we have that if the chain is lazy in a certain sense as well as reversible, then T(1 2) is equivalent to the chain’s mixing time, answering a question of Peres. We furthermore demonstrate that the inequalities we establish give an almost everywhere pointwise limiting characterisation of possible hitting time functions T(α) over the domain α ∈ (0, 1 2]. We consider irreducible reversible discrete time Markov chains on a finite state space. Mixing times and hitting times are fundamental parameters of the chain. We relate them by showing that the mixing time of the lazy chain is equivalent to the maximum over initial states (x ) and large sets (A ) of the hitting time of (A ) starting from (x ). We also prove that the first time when averaging over two consecutive time steps is close to stationarity is equivalent to the mixing time of the lazy version of the chain. Let @math . We show that that the mixing time of a continuous-time Markov chain on a finite state space is about as large as the largest expected hitting time of a subset of the state space with stationary measure @math . Suitably modified results hold in discrete time and or without the reversibility assumption. The key technical tool in the proof is the construction of random set @math such that the hitting time of @math is a light-tailed stationary time for the chain. We note that essentially the same results were obtained independently by Peres and Sousi.