2012/09/28 by Simon Griffiths, Ross J. Kang, Roberto I. Oliveira +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Inequality #Markov Chains and Monte Carlo Methods #Markov chain #Mathematical analysis #Mathematics #Programming language #Set (abstract data type) #Statistics #math.CO #math.PR #msc:60J10
paper · pdf · doi:10.1090/s0002-9939-2014-12045-4
published as Proc. AMS 142(9): 3285-3298, 2014 · 14 pages, 3 figures; v2 includes a new proof of Prop 1.4 due to Peres and Sousi; to appear in Proc. AMS
arxiv created 2012/09/28 · openalex publication_date 2014/05/21 · arxiv updated 2015/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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(α )</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">α</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">α ∈ (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(α )</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">α</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(α ) ≤ T(1/2)/α</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>></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">α > 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(α )</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>