Mixing and hitting times for finite Markov chains

By Roberto Imbuzeiro Oliveira. 2011

57 citations recorded by the source corpus.

Let $0<\alpha<1/2$. 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 $\geq \alpha$. 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 $A$ such that the hitting time of $A$ is a light-tailed stationary time for the chain. We note that essentially the same results were obtained independently by Peres and Sousi.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/837a914b9564710d325ac14dc4f16b3a871cb4bf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Markov Chains and Mixing Times: Second Edition (2017, background): “Peres and Revelle (2004) show cutoff at tcov(Gn) for the lamplighter chain when the base graph is Gn = Z(2)n.”
Mixing Times are Hitting Times of Large Sets (2011, background): “1 was also proved independently by Roberto Imbuzeiro Oliveira ([9]).”