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 α ∈ (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].