Theorem D — Metastability

Open source document →

1. #1

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

   $$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).$$
2. #2

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

   $$\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)}$$
3. #3

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

   $$\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).$$
4. #4

   In the worst case (taking to be itself with absorbing exterior), the effective conductance is bounded by . More precisely, for any with :

   $$\Phi_F(S)\le\frac{\mathrm{cut}_t(S,\bar S)}{\mathrm{vol}_t(S)}\le\phi_t(S).$$
5. #5

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

   $$\mathbb{E}_{\pi_F}[T_{\mathrm{esc}}]\ge\frac{1}{2\tilde\gamma_F}\ge\frac{1}{2\theta}.$$