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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T left-parenthesis alpha right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>α</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">T(\alpha )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of a set of stationary measure at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha"> <mml:semantics> <mml:mi>α</mml:mi> <mml:annotation encoding="application/x-tex">\alpha</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha element-of left-parenthesis 0 comma 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha \in (0,1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We obtain tight inequalities among the values of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T left-parenthesis alpha right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>α</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">T(\alpha )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for different choices of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha"> <mml:semantics> <mml:mi>α</mml:mi> <mml:annotation encoding="application/x-tex">\alpha</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. One consequence is that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T left-parenthesis alpha right-parenthesis less-than-or-equal-to upper T left-parenthesis 1 slash 2 right-parenthesis slash alpha"> <mml:semantics> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>α</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>≤</mml:mo> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>α</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">T(\alpha ) \le T(1/2)/\alpha</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha greater-than 1 slash 2"> <mml:semantics> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha &gt; 1/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. As a corollary we have that if the chain is lazy in a certain sense as well as reversible, then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T left-parenthesis 1 slash 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">T(1/2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T left-parenthesis alpha right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>α</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">T(\alpha )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> over the domain <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha element-of left-parenthesis 0 comma 1 slash 2 right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha \in (0,1/2]</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.