Main Theorems A–H

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}.$$
6. #6

   (ii) Case . The optimal gauge satisfies the linear system (Theorem 7.11). The residual angles are . These solve:

   $$\tilde\alpha = (I-B^T L^\dagger B\,\mathrm{diag}(W))\,\alpha =: \Pi\,\alpha.$$
7. #7

   The operator is the projection onto the cycle space of the graph. The residual curvature at node is:

   $$\rho(i) = \sum_{j\sim i}W_t(i,j)\,\tilde\alpha_{ij}^2.$$
8. #8

   The source of non-zero is the curvature (holonomy around cycles). Near doors, the cycles passing through the exterior create non-trivial holonomy. The Green's function of the graph Laplacian on has the well-known decay property: for a graph with spectral gap ,

   $$|L^\dagger(i,j)|\le\frac{C_0}{\mathrm{vol}(F^\circ)}\cdot e^{-\sqrt{\lambda_2}\,d_{\mathrm{graph}}(i,j)}$$
9. #9

   At the optimal gauge , the Euler--Lagrange equation on each node reads:

   $$\sum_{j\sim i}W_t(i,j)\,\nabla_{h(i)}d_G(g_t^h(i,j),e)^2=0.$$
10. #10

    The energy on is then controlled by a discrete maximum principle: interior values of cannot exceed boundary values (door-adjacent). Summing:

    $$\sum_{i\in F_{\mathrm{deep}}}\rho(i)\le\frac{|F_{\mathrm{deep}}|}{|F_{\mathrm{near}}|}\cdot\mu\cdot\sum_{i\in F_{\mathrm{near}}}\rho(i)$$
11. #11

    Denominator perturbation: .

    $$|\phi'-\phi|=\left|\frac{\mathrm{cut}+\Delta_c}{\mathrm{vol}+\Delta_v}-\frac{\mathrm{cut}}{\mathrm{vol}}\right|=\left|\frac{\Delta_c\cdot\mathrm{vol}-\mathrm{cut}\cdot\Delta_v}{(\mathrm{vol}+\Delta_v)\cdot\mathrm{vol}}\right|.$$