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)}(i,j\in F),{\tilde{P}}_F:=\frac{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:=\underset{\varnothing \ne S⊊F}{\min }\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 {\varphi }_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 }.$$