Theorem D — Metastability

Prerequisites: Theorem A (energy isolation), Sinclair–Jerrum bound (Fact B.6).

Theorem D. Let $F \in F_{t}$ and $X_{0} \sim π_{F}$ . The escape time from $F$ under the lazy walk $\tilde{P}_{t}$ satisfies: $E [T_{esc} (F)] \geq \frac{1}{2 θ} .$

Proof. (Complete.)

Step 1 (Restricted chain). Define the restricted sub-stochastic matrix on $F$ :

P_{F} (i, j) := \frac{W _{t} ( i , j )}{d _{t} ( i )} (i, j \in F), \tilde{P}_{F} := \frac{1}{2} (I ∣_{F} + P_{F}) .

Row sums: $\sum_{j \in F} \tilde{P}_{F} (i, j) = \frac{1}{2} (1 + 1 - r_{F, t} (i)) = 1 - \frac{r _{F, t} ( i )}{2} < 1$ .

Step 2 (Conductance bound). The conductance of the restricted chain on $F$ (with absorbing boundary) is:

Φ_{F} := \emptyset \neq = S ⊊ F min \frac{\sum _{i \in S} \sum _{j \in F ∖ S} P ~ _{F} ( i , j ) π _{F} ( i ) + \sum _{i \in S} \frac{r _{F, t} ( i )}{2} π _{F} ( i )}{π _{F} ( S )}

where $π_{F} (i) \propto d_{t} (i)$ restricted to $F$ .

The numerator's first term is the internal flow out of $S$ within $F$ ; the second term is the leakage from $S$ to the exterior. Consider the cut of $S$ within the full graph. For any $S ⊊ F$ :

i \in S \sum j \in / S \sum P_{t} (i, j) π_{F} (i) = \frac{cut _{t} ( S , V ∖ S )}{vol _{t} ( F )} \cdot vol_{t} (S) .

In the worst case (taking $S$ to be $F$ itself with absorbing exterior), the effective conductance is bounded by $ϕ_{t} (F)$ . More precisely, for any $S ⊊ F$ with $vol_{t} (S) \leq \frac{1}{2} vol_{t} (F)$ :

Φ_{F} (S) \leq \frac{cut _{t} ( S , S ˉ )}{vol _{t} ( S )} \leq ϕ_{t} (S) .

Taking the minimum over $S$ : $Φ_{F} \leq ϕ_{t} (F) \leq θ$ .

Step 3 (Spectral gap). By the Sinclair–Jerrum bound (Fact B.6): $γ_{F} \leq 2 Φ_{F} \leq 2 θ$ . For the lazy chain: $\tilde{γ}_{F} = γ_{F} /2 \leq θ$ .

Step 4 (Escape time). The expected absorption time from the quasi-stationary distribution satisfies (see Aldous–Fill, Theorem 12.4; or Montenegro–Tetali, Theorem 3.3):

E_{π_{F}} [T_{esc}] \geq \frac{1}{2 γ ~ _{F}} \geq \frac{1}{2 θ} .

The factor $\frac{1}{2}$ arises because, for a lazy chain with spectral gap $\tilde{γ}$ , the relaxation time is $1/ \tilde{γ}$ , and the mean hitting time to an absorbing set from the stationary distribution is at least $\frac{1}{2} \cdot \frac{1}{γ ~}$ (Aldous–Fill inequality for reversible absorbing chains). $□$

Explicit constant. The bound $\frac{1}{2 θ}$ is tight up to constant factors. For a barbell graph (two complete graphs of size $n /2$ connected by a single edge of weight $ϵ$ ), the conductance is $Θ (ϵ / n)$ and the escape time is $Θ (n / ϵ)$ .