Drift theorems: from an expected potential drop to absorption #
Let Ψ ≥ 0 be a potential on a finite chain that vanishes exactly on the absorbed states, and
that stays zero once it is zero. Two ways to turn its expected one-step behaviour into a bound
on the absorption time, both from Berenbrink, Giakkoupis, Kermarrec, Mallmann-Trenn, Bounds on
the voter model in dynamic networks, ICALP 2016, [arXiv:1603.01895]:
- Drift
c / Ψ(Lemma 2.2, used there withΨ = √vol(minority)andc_t = d_min φ_t / 32from Lemma 2.1): if𝔼[Ψ_{t+1} | X_t = x] ≤ Ψ x - c_t / Ψ xwheneverΨ x > 0, then the chain is absorbed at timeTwith probability at least1/2as soon as∑_{t < T} c_t ≥ 4 Ψ(x₀)². The proof iterates on𝔼[Ψ_t]: by Jensen (Cauchy–Schwarz),𝔼[Ψ_{t+1}] ≤ 𝔼[Ψ_t] - c_t P(Ψ_t > 0)² / 𝔼[Ψ_t], so𝔼[Ψ_t]would become negative if the survival probability stayed above1/2. No concentration is used. (drift_absorption_seq,drift_absorption.) - Multiplicative drift (the argument of Lemma 2.4): if
𝔼[Ψ_{t+1} | X_t = x] ≤ (1 - δ_t) Ψ xfor every state, then𝔼[Ψ_T] ≤ ∏_{t < T} (1 - δ_t) Ψ(x₀)and, by Markov's inequality, the chain survives to timeTwith probability at most∏_{t < T} (1 - δ_t) Ψ(x₀) / Ψ_min, whereΨ_minbounds the nonzero values ofΨfrom below. (multiplicative_drift_seq,multiplicative_drift; with∏ (1 - δ_t) ≤ exp (-∑ δ_t),multiplicative_drift_seq_exp.)
The _seq versions allow a time-dependent chain (iterateSeq) and time-dependent drift, as for
the dynamic graphs of the paper; the others are their time-homogeneous specializations, stated
with Kernel.event.
Fixed-time drift with an additive error (iterate_le_of_drift, and expList_le_of_drift for
round-based processes): if one step maps φ to at most ρ φ + ε in expectation, with
0 ≤ ρ ≤ 1 and ε ≥ 0, then after T steps the expected potential is at most ρ^T φ + T ε.
Contraction on a closed region (iterate_le_pow_of_closed): if the chain cannot leave a
region R and one step contracts Ψ by θ on R, then t steps contract it by θ^t on R;
observables ordered on R have ordered expectations from R (iterate_le_of_closed).
Drift lemma, time-dependent form (Lemma 2.2 of Berenbrink, Giakkoupis, Kermarrec,
Mallmann-Trenn, ICALP 2016). Let Ψ ≥ 0. Suppose that for every step t < T, the kernel K t
lowers Ψ in expectation by at least c t / Ψ x from every state x with Ψ x > 0, and keeps
Ψ at zero from every state with Ψ x = 0. If ∑_{t < T} c t ≥ 4 Ψ(x₀)², then started at x₀
the chain has Ψ = 0 (is absorbed) at time T with probability at least 1/2.
Drift lemma (Lemma 2.2 of Berenbrink, Giakkoupis, Kermarrec, Mallmann-Trenn, ICALP 2016,
for a single kernel). Let Ψ ≥ 0 satisfy 𝔼[Ψ_{t+1} | X_t = x] ≤ Ψ x - c / Ψ x whenever
Ψ x > 0, and let the states with Ψ = 0 be absorbing for Ψ. Then the chain started at x₀
is absorbed by every time T with c T ≥ 4 Ψ(x₀)², with probability at least 1/2.
Multiplicative drift, time-dependent form (the argument of Lemma 2.4 of Berenbrink,
Giakkoupis, Kermarrec, Mallmann-Trenn, ICALP 2016). Let Ψ ≥ 0, with every nonzero value at
least Ψmin > 0. If for every step t < T the kernel K t satisfies
𝔼[Ψ_{t+1} | X_t = x] ≤ (1 - δ t) Ψ x from every state x (absorbed ones included), then the
chain started at x₀ still has Ψ > 0 at time T with probability at most
∏_{t < T} (1 - δ t) Ψ(x₀) / Ψmin.
Multiplicative drift (the argument of Lemma 2.4 of Berenbrink, Giakkoupis, Kermarrec,
Mallmann-Trenn, ICALP 2016, for a single kernel). Let Ψ ≥ 0, with every nonzero value at least
Ψmin > 0, and 𝔼[Ψ_{t+1} | X_t = x] ≤ (1 - δ) Ψ x from every state. Then the chain started at
x₀ is not absorbed at time T with probability at most (1 - δ)^T Ψ(x₀) / Ψmin.
Multiplicative drift, exponential form. Under the hypotheses of
multiplicative_drift_seq, with every rate δ t ≤ 1, the chain started at x₀ still has
Ψ > 0 at time T with probability at most exp (-∑_{t < T} δ t) Ψ(x₀) / Ψmin.
Fixed-time drift with an additive error #
Fixed-time drift. If one step of K maps the potential φ to at most ρ φ + ε, with
0 ≤ ρ ≤ 1 and 0 ≤ ε, then after T steps the expected potential is at most
ρ ^ T φ + T ε.
Contraction on a closed region #
Comparison on a closed region. If the region Q is closed under the transitions of K
(every state of positive weight from a state of Q is in Q) and F ≤ F' on Q, then
𝔼_x F(X_n) ≤ 𝔼_x F'(X_n) from every state x of Q.
Contraction on a closed region. If the region R is closed under the transitions of K
and one step contracts the potential Ψ by θ ≥ 0 from every state of R, then t steps
contract it by θ ^ t from every state of R.
Fixed-time drift for a round-based process: if one uniform round maps the potential φ
to at most ρ φ + ε in expectation (0 ≤ ρ ≤ 1, 0 ≤ ε), then after T rounds the expected
potential is at most ρ ^ T φ + T ε.