Tight inequalities among set hitting times in Markov chains

Abstract

Given an irreducible discrete-time Markov chain on a finite state space, we consider the largest expected hitting time $T(\alpha )$ of a set of stationary measure at least $\alpha$ for $\alpha \in (0,1)$. We obtain tight inequalities among the values of $T(\alpha )$ for different choices of $\alpha$. One consequence is that $T(\alpha )\le T(1/2)/\alpha$ for all $\alpha <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(\alpha )$ over the domain $\alpha \in (0,1/2]$.

14 pages, 3 figures; v2 includes a new proof of Prop 1.4 due to Peres and Sousi; to appear in Proc. AMS

References in corpus (1)

• Mixing and hitting times for finite Markov chains

Cited by in corpus (10)

• Characterization of cutoff for reversible Markov chains
• Mixing times are hitting times of large sets
• Mixing time bounds via bottleneck sequences
• The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and Fill
• Dimension-free Mixing for High-dimensional Bayesian Variable Selection
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• A spectral characterization for concentration of the cover time
• Missing Mass Concentration for Markov Chains
• Mixing times and moving targets
• Cutoff for random walk on random graphs with a community structure