Tight inequalities among set hitting times in Markov chains

Original · EN

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].