Documentation

ThreeMajority.ManyOpinionsDrift

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

The general facts on hitting probabilities used here (hitProb_le_one, hitProb_mono_time) are in Dynamics.Hitting.

theorem ThreeMajority.hitProb_mul_le_event {α : Type u_1} [Fintype α] (K : Dynamics.Kernel α) {B P : α → Prop} (habs : ∀ (a : α), P a → (K a).prob P = 1) {s : ℕ} {q : ℝ} (hB : ∀ (b : α), B b → q ≤ K.event P s b) (t : ℕ) (a : α) :
q * K.hitProb B t a ≤ K.event P (t + s) a

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

theorem ThreeMajority.expect_le_expect_of_prob_eq_one {α : Type u_1} [Fintype α] (p : Dynamics.Distribution α) {I : α → Prop} (hp : p.prob I = 1) {g h : α → ℝ} (hgh : ∀ (x : α), I x → g x ≤ h x) :
p.expect g ≤ p.expect h

A distribution giving probability one to I has expectations monotone on I.

theorem ThreeMajority.iterate_le_iterate_of_invariant {α : Type u_1} [Fintype α] (K : Dynamics.Kernel α) {I : α → Prop} (hI : ∀ (x : α), I x → (K x).prob I = 1) {g h : α → ℝ} (hgh : ∀ (x : α), I x → g x ≤ h x) (s : ℕ) (x : α) :
I x → K.iterate s g x ≤ K.iterate s h x

The iterates of a kernel that keeps I with probability one are monotone on I.

theorem ThreeMajority.hitProb_additive_drift {α : Type u_1} [Fintype α] (K : Dynamics.Kernel α) (I B : α → Prop) (f : α → ℝ) {lam β M η : ℝ} (hβ : 0 ≤ β) (hη : 0 ≤ η) (hI : ∀ (x : α), I x → (K x).prob I = 1) (hfM : ∀ (x : α), I x → f x ≤ M) (hfβ : ∀ (x : α), I x → ¬B x → f x ≤ β) (hdrift : ∀ (x : α), I x → ¬B x → f x + lam ≤ K.apply f x) (hjump : ∀ (x : α), I x → ¬B x → ((K x).prob fun (y : α) => β < f y) ≤ η) (t : ℕ) (a : α) (ha : I a) (hfa : 0 ≤ f a) :
lam * ↑t * (1 - K.hitProb B t a) ≤ β + M * η * ↑t

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.