Skip to main content
Jaehong Oh

ℓPart 2· Theorem D

Theorem D — Metastability

472 words2 min read

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

Theorem D. Let F∈FtF\in\mathfrak{F}_t and X0∼πFX_0\sim\pi_F. The escape time from FF under the lazy walk P~t\tilde P_t satisfies: E[Tesc(F)]  ≥  12θ.\mathbb{E}[T_{\mathrm{esc}}(F)]\;\ge\;\frac{1}{2\theta}.

Proof. (Complete.)

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

PF(i,j):=Wt(i,j)dt(i)(i,j∈F),P~F:=12(I∣F+PF).P_F(i,j):=\frac{W_t(i,j)}{d_t(i)}\quad(i,j\in F),\qquad\tilde P_F:=\tfrac{1}{2}(I|_F+P_F).

Row sums: ∑j∈FP~F(i,j)=12(1+1−rF,t(i))=1−rF,t(i)2<1\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 FF (with absorbing boundary) is:

ΦF:=min⁡∅≠S⊊F∑i∈S∑j∈F∖SP~F(i,j)πF(i)+∑i∈SrF,t(i)2πF(i)πF(S)\Phi_F:=\min_{\emptyset\ne S\subsetneq F}\frac{\sum_{i\in S}\sum_{j\in F\setminus S}\tilde P_F(i,j)\pi_F(i)+\sum_{i\in S}\frac{r_{F,t}(i)}{2}\pi_F(i)}{\pi_F(S)}

where πF(i)∝dt(i)\pi_F(i)\propto d_t(i) restricted to FF.

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

∑i∈S∑j∉SPt(i,j)πF(i)=cutt(S,V∖S)volt(F)⋅volt(S).\sum_{i\in S}\sum_{j\notin S}P_t(i,j)\pi_F(i) = \frac{\mathrm{cut}_t(S,V\setminus S)}{\mathrm{vol}_t(F)}\cdot\mathrm{vol}_t(S).

In the worst case (taking SS to be FF itself with absorbing exterior), the effective conductance is bounded by ϕt(F)\phi_t(F). More precisely, for any S⊊FS\subsetneq F with volt(S)≤12volt(F)\mathrm{vol}_t(S)\le\frac{1}{2}\mathrm{vol}_t(F):

ΦF(S)≤cutt(S,Sˉ)volt(S)≤ϕt(S).\Phi_F(S)\le\frac{\mathrm{cut}_t(S,\bar S)}{\mathrm{vol}_t(S)}\le\phi_t(S).

Taking the minimum over SS: ΦF≤ϕt(F)≤θ\Phi_F\le\phi_t(F)\le\theta.

Step 3 (Spectral gap). By the Sinclair–Jerrum bound (Fact B.6): γF≤2ΦF≤2θ\gamma_F\le 2\Phi_F\le 2\theta. For the lazy chain: γ~F=γF/2≤θ\tilde\gamma_F=\gamma_F/2\le\theta.

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[Tesc]≥12γ~F≥12θ.\mathbb{E}_{\pi_F}[T_{\mathrm{esc}}]\ge\frac{1}{2\tilde\gamma_F}\ge\frac{1}{2\theta}.

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

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