Progress through nested phases #
A finite Markov chain that, from every state of Aᵢ, stays in Aᵢ with
probability ≥ 1 - ε and moves into the smaller set Aᵢ₊₁ with
probability ≥ 1 - ν, reaches the innermost set A_T within ℓ T steps
except with probability T (ℓ ε + ν^ℓ). This is Lemma A.4 of Becchetti,
Clementi, Natale, Pasquale, Silvestri, Trevisan, Simple dynamics for
plurality consensus (SPAA 2014); its proof is omitted there.
The proof works phase by phase with the survival observable outside B
(the indicator of having left B): within ℓ steps the chain leaves Aᵢ
with probability at most ℓ ε and fails to jump in each of the ℓ steps
with probability at most ν^ℓ. The hypothesis ε ≤ ν of the paper is not
needed.
Phase calculus with a potential (iterate_outside_le_of_phases): if every set A j is
closed under the chain and, for j < J, one step from A j enters A (j + 1) with probability
at least 1 - q, then from A 0 the chain is outside A J after t steps with probability at
most (q + 1/λ)^t λ^J, for every λ ≥ 1. The potential is λ^{J - j} in phase j (the largest
j ≤ J with the state in A j, phaseOf) and 0 in A J (phasePot); it contracts by
q + 1/λ per step, and iterate_le_pow_of_closed iterates the contraction. The sets need not
be nested, and the bound is exponential in t rather than a union bound over the phases.
Staying: if from every state of B the chain stays in B with
probability ≥ 1 - ε, then it has left B after ℓ steps with probability
at most ℓ ε.
One phase: from A, which is left with probability ≤ ε per step,
the chain is outside B ⊆ A after ℓ steps with probability at most
ℓ ε + ν^ℓ, if every step from A enters B with probability ≥ 1 - ν and
B itself is left with probability ≤ ε per step.
Lemma A.4 (nested phases). Let A₁ ⊇ A₂ ⊇ ⋯ ⊇ A_T be such that
from every state of Aᵢ the chain stays in Aᵢ with probability
≥ 1 - ε, and for i < T moves into Aᵢ₊₁ with probability ≥ 1 - ν.
Then from any state of A₁, after ℓ T steps the chain lies in A_T with
probability at least 1 - T (ℓ ε + ν^ℓ).
Phase calculus with a potential #
The phase of a: the largest j ≤ J with a ∈ A j (0 if there is none).
Equations
- Dynamics.Kernel.phaseOf A J a = Nat.findGreatest (fun (j : ℕ) => a ∈ A j) J
Instances For
One step of the phase potential contracts it by q + 1/λ from every state of A 0.
Phase calculus. Let every set A j (j ≤ J) be closed under the chain, and let one step
from A j enter A (j + 1) with probability at least 1 - q for j < J. Then from any state
of A 0, the chain is outside A J after t steps with probability at most
(q + 1/λ)^t λ^J, for every λ ≥ 1.