Mixing times are hitting times of large sets

2011/07/31 by Yuval Peres, Peres, Yuval, Perla Sousi +1 · 1 citation
Mathematics · Chemistry · Biochemistry, Genetics and Molecular Biology · #Markov Chains and Monte Carlo Methods #Mass Spectrometry Techniques and Applications #Protein Structure and Dynamics

paper · pdf · doi:10.48550/arxiv.1108.0133

Abstract

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.

Cited by

• Mixing time bounds for oriented kinetically constrained spin models

Related

• Mixing Times and Hitting Times for General Markov Processes
• Intersection and mixing times for reversible chains
• Elementary Bounds On Mixing Times for Decomposable Markov Chains
• A Lower Bound on the Mixing Time of Uniformly Ergodic Markov Chains in Terms of the Spectral Radius
• Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path