Hitting times under an additive drift (BCNPT16, Lemma 3.2; roadmap MAJ-12 (a)) #
Facts about an arbitrary finite Markov kernel K, for the symmetry-breaking stage of 3-Majority
with many colours (Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with
many opinions, SODA 2016, arXiv:1508.06782, BCNPT16 below).
hitProb_additive_drift: Lemma 3.2 of BCNPT16 in finite-horizon form. If, inside an invariant setIand outside the targetB, an observablef ≤ Mgrows by at leastλin expectation per step, is at mostβoutsideB, and overshootsβin one step with probability at mostη, thenλ t P(T_B > t) ≤ β + M η t. The paper states𝔼[T_B] ≤ 2 α m / λ(β = α m, with the overshoot controlled at the hitting time, its Hypothesis 2 and Lemma B.1) and then applies Markov's inequality; here the overshoot is controlled one step at a time and no infinite-horizon expectation is needed.hitProb_mul_le_event(hit, then absorb, multiplicative form): if from every state ofBthe chain is in an absorbing eventPafterssteps with probability at leastq, then it is inPat timet + swith probability at leastq P(T_B ≤ t)(the strong Markov property at the hitting time ofB, by induction ont;Dynamics.Kernel.hitProb_sub_le_eventis the additive formP(T_B ≤ t) − ε).
The general facts on hitting probabilities used here (hitProb_le_one, hitProb_mono_time) are
in Dynamics.Hitting.
Hit, then absorb (multiplicative form). Let P be absorbing for K. If from every state
of B the chain is in P after s steps with probability at least q, then from any state
a it is in P at time t + s with probability at least q P_a(T_B ≤ t).
The iterates of a kernel that keeps I with probability one are monotone on I.
Lemma 3.2 (BCNPT16), finite-horizon form. Let I be invariant for K and let B be a
target set. Suppose that, for every x ∈ I, f x ≤ M, and for every x ∈ I outside B:
f x ≤ β; the drift 𝔼[f(X₁) | X₀ = x] ≥ f x + λ (Hypothesis 1); and the overshoot
P(f(X₁) > β | X₀ = x) ≤ η (the one-step form of Hypothesis 2). Then for every start a ∈ I
with f a ≥ 0 and every t, λ t P_a(T_B > t) ≤ β + M η t.
In the paper B = {f ≥ m}, β = α m, the conclusion is 𝔼_a[T_B] ≤ 2 α m / λ, and the
symmetry-breaking stage (Lemma 3.3) applies Markov's inequality to it.