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(α)$ of a set of stationary measure at least $α$ for $α\in(0,1)$. We obtain tight inequalities among the values of $T(α)$ for different choices of $α$. One consequence is that $T(α) \le 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 $α\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