Documentation

Dynamics.Drift

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]:

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

theorem Dynamics.Kernel.drift_absorption_seq {α : Type u_1} [Fintype α] (K : ℕ → Kernel α) (Ψ : α → ℝ) (c : ℕ → ℝ) (T : ℕ) (hΨ : ∀ (x : α), 0 ≤ Ψ x) (hc : ∀ t < T, 0 ≤ c t) (hdrift : ∀ t < T, ∀ (x : α), 0 < Ψ x → (K t).apply Ψ x ≤ Ψ x - c t / Ψ x) (habs : ∀ t < T, ∀ (x : α), Ψ x = 0 → (K t).apply Ψ x = 0) (x₀ : α) (hT : 4 * Ψ x₀ ^ 2 ≤ ∑ t ∈ Finset.range T, c t) :
1 / 2 ≤ iterateSeq K T (fun (x : α) => if Ψ x = 0 then 1 else 0) x₀

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.

theorem Dynamics.Kernel.drift_absorption {α : Type u_1} [Fintype α] (K : Kernel α) (Ψ : α → ℝ) {c : ℝ} (hc : 0 ≤ c) (hΨ : ∀ (x : α), 0 ≤ Ψ x) (hdrift : ∀ (x : α), 0 < Ψ x → K.apply Ψ x ≤ Ψ x - c / Ψ x) (habs : ∀ (x : α), Ψ x = 0 → K.apply Ψ x = 0) (x₀ : α) {T : ℕ} (hT : 4 * Ψ x₀ ^ 2 ≤ c * ↑T) :
1 / 2 ≤ K.event (fun (x : α) => Ψ x = 0) T x₀

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.

theorem Dynamics.Kernel.multiplicative_drift_seq {α : Type u_1} [Fintype α] (K : ℕ → Kernel α) (Ψ : α → ℝ) (δ : ℕ → ℝ) (T : ℕ) {Ψmin : ℝ} (hΨ : ∀ (x : α), 0 ≤ Ψ x) (hmin : 0 < Ψmin) (hgap : ∀ (x : α), 0 < Ψ x → Ψmin ≤ Ψ x) (hdrift : ∀ t < T, ∀ (x : α), (K t).apply Ψ x ≤ (1 - δ t) * Ψ x) (x₀ : α) :
iterateSeq K T (fun (x : α) => if 0 < Ψ x then 1 else 0) x₀ ≤ (∏ t ∈ Finset.range T, (1 - δ t)) * Ψ x₀ / Ψmin

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.

theorem Dynamics.Kernel.multiplicative_drift {α : Type u_1} [Fintype α] (K : Kernel α) (Ψ : α → ℝ) {δ Ψmin : ℝ} (hΨ : ∀ (x : α), 0 ≤ Ψ x) (hmin : 0 < Ψmin) (hgap : ∀ (x : α), 0 < Ψ x → Ψmin ≤ Ψ x) (hdrift : ∀ (x : α), K.apply Ψ x ≤ (1 - δ) * Ψ x) (x₀ : α) (T : ℕ) :
K.event (fun (x : α) => 0 < Ψ x) T x₀ ≤ (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.

theorem Dynamics.Kernel.multiplicative_drift_seq_exp {α : Type u_1} [Fintype α] (K : ℕ → Kernel α) (Ψ : α → ℝ) (δ : ℕ → ℝ) (T : ℕ) {Ψmin : ℝ} (hΨ : ∀ (x : α), 0 ≤ Ψ x) (hmin : 0 < Ψmin) (hgap : ∀ (x : α), 0 < Ψ x → Ψmin ≤ Ψ x) (hδ : ∀ t < T, δ t ≤ 1) (hdrift : ∀ t < T, ∀ (x : α), (K t).apply Ψ x ≤ (1 - δ t) * Ψ x) (x₀ : α) :
iterateSeq K T (fun (x : α) => if 0 < Ψ x then 1 else 0) x₀ ≤ Real.exp (-∑ t ∈ Finset.range T, δ 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 #

theorem Dynamics.Kernel.iterate_le_of_drift {α : Type u_1} [Fintype α] (K : Kernel α) (φ : α → ℝ) {ρ ε : ℝ} (hρ0 : 0 ≤ ρ) (hρ1 : ρ ≤ 1) (hε : 0 ≤ ε) (hφ : ∀ (a : α), K.apply φ a ≤ ρ * φ a + ε) (T : ℕ) (a : α) :
K.iterate T φ a ≤ ρ ^ T * φ a + ↑T * ε

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 #

theorem Dynamics.Kernel.iterate_le_of_closed {α : Type u_1} [Fintype α] (K : Kernel α) (Q : α → Prop) (hQ : ∀ (y z : α), Q y → (K y).weight z ≠ 0 → Q z) {F F' : α → ℝ} (hF : ∀ (y : α), Q y → F y ≤ F' y) (n : ℕ) (x : α) :
Q x → K.iterate n F x ≤ K.iterate n F' x

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.

theorem Dynamics.Kernel.iterate_le_pow_of_closed {α : Type u_1} [Fintype α] (K : Kernel α) (R : α → Prop) (hR : ∀ (a b : α), R a → (K a).weight b ≠ 0 → R b) (Ψ : α → ℝ) {θ : ℝ} (hθ : 0 ≤ θ) (hstep : ∀ (a : α), R a → K.apply Ψ a ≤ θ * Ψ a) (t : ℕ) (a : α) :
R a → K.iterate t Ψ a ≤ θ ^ t * Ψ a

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.

theorem Dynamics.expList_le_of_drift {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) (φ : S → ℝ) {ρ ε : ℝ} (hρ0 : 0 ≤ ρ) (hρ1 : ρ ≤ 1) (hε : 0 ≤ ε) (hφ : ∀ (s : S), (avg fun (r : R) => φ (step s r)) ≤ ρ * φ s + ε) (T : ℕ) (s : S) :
(expList R T fun (l : List R) => φ (List.foldl step s l)) ≤ ρ ^ T * φ s + ↑T * ε

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