Proof For $i\in \{0,1\}$ , we let $P_i$ be the transition matrix corresponding to $W_i$ . We denote

\begin{align*} w^i_u = \sum_{e\ni u}w^i_e, \quad \quad Z_i = \sum_{u\in V} w^i_u. \end{align*}

We also denote by $\pi^i$ the stationary distribution of $W_i$ and recall that $\pi^i(u) = w^i_u / Z_i$ . We will now use Lemma 2.6 to show that $\gamma^1 \leq \gamma^0$ . A simple calculation shows that for every f

(5) \begin{equation} \mathcal{E}^{P_1}_{\pi^1}(f) = \frac{1}{2}\sum_{u,v\in V}\frac{w^1_{u,v}}{Z_1}(f(u)-f(v))^2 = \frac{Z_0}{Z_1}\mathcal{E}^{P_0}_{\pi^0}(f). \end{equation}

Also, we write $\varepsilon = w^1_{vv} - w^0_{vv} > 0$ . Then, for every $u \in V$ we have

\begin{equation*} \frac{\pi^0(u)}{\pi^1(u)} = \frac{\frac{w_u^0}{Z_0}}{\frac{w_u^1}{Z_1}} = \begin{cases} \dfrac{Z_1}{Z_0} & u\neq v \\ \\[-9pt] \dfrac{Z_1}{Z_0}\cdot \dfrac{w_v^0}{w_v^0 + \varepsilon} & u = v \end{cases}. \end{equation*}

Hence, in any case $\pi^0(u)/\pi^1(u) \leq Z_1/Z_0$ . By (5), we can use Lemma 2.6 with $\alpha = Z_0 / Z_1$ . We thus get that $\gamma^1 \leq \gamma^0$ .

Proof Let $(G,w^\alpha)$ be the network associated with the graph G such that $w^\alpha_{uv} = 1$ if $(u,v)\in E$ and $w^\alpha_{vv} = \beta_v$ where $\beta_v$ satisfies $\frac{\beta_v}{\deg\!(v) + \beta_v} = \alpha$ . If P is the transition matrix of the simple random walk on G, then $Q\,{:\!=}\, \alpha I + (1-\alpha)P$ is the transition matrix corresponding to $(G,w^\alpha)$ . Note that the spectral gap of Q satisfies $\gamma(Q) = (1-\alpha)\gamma(P)$ . Let $(p_v)_{v\in V}$ be the lazy vector with all values non-negative and smaller than $\alpha$ . The random walk that stays put at some $u\in V$ with probability $p_u$ and jumps according to P otherwise can be seen as a random walk on a network $(G,w^p)$ which can be constructed from $(G,w^\alpha)$ by going iteratively over all vertices $v\in V$ and decreasing the weight of $w^\alpha_{vv}$ at each step according to $p_v$ . By Claim 2.7, at each step the spectral gap can be only increased. Hence, the spectral gap of the walk corresponding to $(G,w^p)$ is larger than $\gamma(Q) = (1-\alpha)\gamma(P)$ , as required.

Proof of Lemma 2.4. When $k=1$ , this is trivial and the spectral gap of G is at least a. We assume henceforth that $k\geq 2$ and we consider the projection and restriction chains associated with the decomposition of V to sets of $\mathcal{P}$ as described earlier in this section. Let $i\in[k]$ and consider the restriction chain associated with $V_i$ , a set of $\mathcal{P}$ . By our assumption, we have that the spectral gap of $G[V_i]$ is at least a. However, the restriction walk on $V_i$ is different from the simple random walk on $G[V_i]$ , as it is obtained from it by adding self loops for every edge that exits $V_i$ . For every $v\in V$ we denote by $p_v$ the probability to move from v to itself in the restriction chain. Since every $v\in V_i$ has $\deg\!(v, V_i) \geq b$ , we have that $p_v \leq (1-\frac{b}{n})$ . We thus have by Claim 2.8 that $\gamma_i$ , the spectral gap of the restriction chain, satisfies $\gamma_i \geq \frac{ab}{n}$ .

We turn to the projection chain, which is a Markov chain on the state space [k] with stationary distribution $\overline{\pi}$ and transition matrix $\overline{P}$ as in (4). We will use Claim 2.9 to bound the spectral gap associated with it from below. For every edge $e = (l,m) \in H(\mathcal{P},c)$ , we denote $Q(e) = \overline{\pi}(l)\overline{P}(l,m)$ . We denote by P the transition matrix of the original simple random walk. By the definition in (4), we have

\begin{equation*} Q(e) = \overline{\pi}(l)\cdot \frac{1}{\overline{\pi}(l)}\sum_{u\in V_l, v\in V_m} \pi(u)P(u,v) = \sum_{u\in V_l} \frac{|E(u,V_m)|}{2|E|} \geq \frac{|E(V_l,V_m)|}{n^2} \geq \frac{c}{n^2}. \end{equation*}

Since the graph $H(\mathcal{P},c)$ is connected, for every $x,y\in[k]$ we can choose a path $\varphi_{x,y}$ connecting x and y such that every edge in this path has $Q(e) \geq c/n^2$ . We choose such paths for every x, y arbitrarily. We obtain that for every edge e which belongs to any path in this choice $(\varphi_{x,y})_{x,y\in[k]}$ we have

\begin{equation*} \frac{1}{Q(e)}\sum_{\varphi_{x,y}\ni e}\overline{\pi}(x)\overline{\pi}(y)|\varphi_{x,y}| \leq \frac{kn^2}{c}\sum_{\varphi_{x,y}\ni e}\overline{\pi}(x)\overline{\pi}(y) \leq \frac{kn^2}{c}. \end{equation*}

Hence, by Claim 2.9, the spectral gap of the projection chain $\overline{\gamma}$ is at least $c/kn^2$ . Using Theorem 2.5, we conclude

\begin{equation*} \gamma \geq \min_{i\in[k]} \frac{\overline{\gamma}\gamma_i}{6} \geq \frac{abc}{6kn^3}. \end{equation*}

Proof We build the decomposition inductively each time refining the partition of V. We begin with the trivial partition $\{V\}$ . At each step, if there is a subset W in the partition that can be further partitioned $W=W_1 \sqcup W_2$ such that $|E(W_1,W_2)| \leq \frac{\delta^3}{20} |W_1||W_2|$ , then we refine the partition by replacing W with $W_1,W_2$ . We call the edges $E(W_1,W_2)$ in each such refinement step negligible. The choice of W and $W_1, W_2$ is not necessarily unique and at each step we choose arbitrarily among all possibilities. Since the graph is finite this process must stop and we denote the final decomposition by $V = U_1 \sqcup \ldots \sqcup U_\ell$ , where edges between any pair $U_i$ and $U_j$ are negligible. The sum of $|W_1||W_2|$ , described above, over each of the $\ell$ refinement steps is no more than the cardinality of pairs of vertices, hence, the number of negligible edges is at most $\frac{\delta^3}{20}\Big(\begin{array}{l} n \\[-7pt] 2 \end{array}\Big)$ .

We call a vertex bad if the number of negligible edges touching it is larger than $\delta n / 2$ . Our bound on the number of negligible edges implies that there are no more than $\delta^2n/10$ bad vertices. Every vertex which is not bad is called good. If a set $U_i$ in the partition contains a good vertex we call it a good set, otherwise, a bad set. Since the minimal degree in the graph is larger than $\delta n$ , every good vertex v touches at least $\delta n / 2$ edges that are not negligible; the corresponding neighbours must be in the same set of the partition as v. Hence each good set is of size at least $\delta n / 2$ and so their number is at most $2/\delta$ . We call bad vertices belonging to bad sets evil. To obtain our primary decomposition, we remove all bad sets from the partition and redistribute the evil vertices among the good sets as follows. Assume without loss of generality that the good sets of the partition are $U_1, \ldots, U_k$ where $k\leq \ell$ . Let $v \in V \setminus \cup_{i=1}^k U_i$ be an evil vertex. Since the number of good neighbours of v is at least $\delta n - \delta^2n/10$ and $k \leq 2/\delta$ , there exists some $i\in[k]$ for which $d(v, U_i) \geq \delta^2 n / 3$ . We add v to one such set chosen arbitrarily.

We denote the resulting decomposition by $V = V_1 \sqcup \ldots \sqcup V_k$ (with $U_i \subset V_i$ for all $i\in[k]$ ) and argue that it satisfies the desired conditions of Definition 2.10. Conditions (1) and (2) are immediate. To see that condition (3) is satisfied, let $i\in[k]$ and let $v\in V_i$ . If v is good, then $\deg\!(v,V_i) \geq \delta n/2$ . If v is bad but not evil, then $|E(\{v\}, U_i)| \geq \frac{\delta^3}{20} |U_i| \geq \delta^4 n / 40$ since otherwise we would have partitioned $U_i$ to $\{v\}$ and $U_i\setminus\{v\}$ . If v is evil, then it was added to $V_i$ since $d(v,U_i)\geq \delta^2 n / 3$ .

It remains to prove condition (4). Due to Cheeger’s inequality (see equation (1)), it is enough to show that for every $i\in[k]$

(6) \begin{equation} \Phi(G[V_i]) \geq \frac{\delta^5}{1200}. \end{equation}

Fix $i\in [k]$ . We slightly abuse notation and write Vol and $\pi$ for the volume and stationary measures on $G[V_i]$ respectively, that is, for any $S\subset V_i$ we have $\textrm{Vol}(S)=\sum _{s \in S} \deg\!(s, V_i)$ and $\pi(S)=\textrm{Vol}(S)/\textrm{Vol}(V_i)$ . Let $X \subset V_i$ be a subset with $\pi(X) \leq 1/2$ . If at least half of the vertices of X are evil, then its size is at most twice the number of bad vertices, i.e. $|X| \leq \delta^2 n / 5$ . Each evil vertex of X has at least $\delta^2n/3 - \delta^2n/5$ of its neighbours in $V_i$ outside X. Hence,

\begin{equation*} \frac{|\partial X|}{\textrm{Vol}(X)} \geq \frac{\frac{2\delta^2n}{15}\cdot\frac{|X|}{2}}{n|X|} = \frac{\delta^2}{15}. \end{equation*}

Suppose otherwise that at least half of the vertices of X are non-evil. Denote the set of non-evil vertices of X by R and let T be the other non-evil vertices of $V_i$ . Note that $R\sqcup T = U_i$ . The number of edges between them is at least $\frac{\delta^3}{20} |R||T|$ , since otherwise $U_i$ would have been partitioned further. Thus,

(7) \begin{equation} \frac{|\partial X|}{\textrm{Vol}(X)} \geq \frac{|E(R,T)|}{\textrm{Vol}(X)} \geq \frac{\frac{\delta^3}{20}|R||T|}{\textrm{Vol}(X)} \geq \frac{\frac{\delta^3}{20} |T| |X|}{2n|X|} \geq \frac{\delta^3|T|}{40n}. \end{equation}

It remains to lower bound $|T|$ . Denote by $G_i$ and $B_i$ the sets of good and bad vertices of $V_i$ , respectively. We have that $|G_i| \geq \delta n/2 - \delta^2 n/10$ . Each vertex $v\in G_i$ has $\deg\!(v,V_i)\geq \delta n/2$ hence $\textrm{Vol}(G_i) \geq \delta^2 n^2/5$ . On the other hand, since the total number of bad vertices is at most $\delta^2 n/10$ we have $\textrm{Vol}(B_i)\leq \delta^2 n^2/10$ . We deduce that $\pi(G_i)\geq 2/3$ . Since $\pi(V_i \setminus X) \geq 1/2$ , we have that $\pi(T) \geq \pi(G_i \cap (V_i \setminus X)) \geq 1/6$ . We bound $\textrm{Vol}(T)\leq |T|n$ and $\textrm{Vol}(V_i)\geq\textrm{Vol}(G_i) \geq \delta^2 n^2/5$ which with the last estimate gives $|T|\geq \delta^2 n /30$ . We plug this into (7) to obtain that $\frac{|\partial X|}{\textrm{Vol}(X)} \geq \frac{\delta^5}{1200}$ , as required.

Proof. Let $\varepsilon>0$ . We will construct $\mathcal{P}$ , an $(\varepsilon,\alpha,\beta)$ -good coarsening of $\mathcal{P}'$ , which will satisfy conditions (1) and (2) of Definition 2.12 with some parameter $\theta$ . At first, if $\mathcal{P}'$ satisfies condition (2) with $\varepsilon$ playing the role of $\theta$ , then $\mathcal{P}'$ is an $(\varepsilon,\alpha,\beta)$ good coarsening of itself. Otherwise, we build recursively a finite sequence of length at most $\ell$ of coarsenings $\langle\mathcal{P}_i\rangle$ of $\mathcal{P}'$ and parameters $\langle\theta_i\rangle$ , such that $\mathcal{P}_i$ satisfies condition (1) with $\theta_i$ . We set $\mathcal{P}_1 \,{:\!=}\, \mathcal{P}'$ and $\theta_1 = \varepsilon$ .

At step $m>1$ , we are given with $\mathcal{P}_{m-1}$ and $\theta_{m-1}$ such that $\mathcal{P}_{m-1}$ satisfies condition (1) with parameter $\theta_{m-1}$ . If $\mathcal{P}_{m-1}$ also satisfies condition (2) with $\theta_{m-1}$ , then $\mathcal{P}_{m-1}$ is an $(\varepsilon,\alpha,\beta)$ good coarsening and we halt the process, denoting $\mathcal{P} \,{:\!=}\, \mathcal{P}_{m-1}$ and $\theta \,{:\!=}\, \theta_{m-1}$ . Otherwise, there exists a set U in the partition $\mathcal{P}_{m-1}$ which has $|E(U,V\setminus U)| \geq \theta_{m-1}^2\alpha\beta$ . Since there are $\ell$ sets in $\mathcal{P}'$ , there exists at least one pair of sets $W_1 \subseteq U$ and $W_2 \subseteq V\setminus U$ , both are sets of the partition $\mathcal{P}'$ , such that $|E(W_1,W_2)| \geq \theta_{m-1}^2\alpha\beta / \ell^2$ . We denote

(8) \begin{equation} \theta_m = \frac{\alpha}{\ell^2}\theta_{m-1}^2 \end{equation}

and form $\mathcal{P}_m$ by replacing U and the set containing $W_2$ in $\mathcal{P}_{m-1}$ with their union. We note that since we assumed that $\mathcal{P}_{m-1}$ is a coarsening of $\mathcal{P}'$ and satisfies condition (1) with $\theta_{m-1}$ , then $\mathcal{P}_m$ is also a coarsening of $\mathcal{P}'$ which satisfies condition (1) with $\theta_m$ .

Eventually, since the number of sets in $\mathcal{P}'$ is $\ell$ , this process halts within at most $\ell$ steps and we obtain an $(\varepsilon,\alpha,\beta)$ good coarsening $\mathcal{P}$ and $\theta$ , a parameter satisfying $\theta \geq \theta_\ell$ , with which conditions (1) and (2) are satisfied. Solving (8) with initial condition $\theta_1 = \varepsilon$ , we obtain

\begin{equation*} \theta_m = \varepsilon\left(\frac{\varepsilon\alpha}{\ell^2}\right)^{2^{m-1}-1}. \end{equation*}

Therefore, we have

\begin{equation*} \theta \geq \theta_{\ell} \geq \varepsilon\left(\frac{\varepsilon\alpha}{\ell^2}\right)^{2^{\ell-1}-1} \geq \varepsilon\left(\frac{\varepsilon\alpha}{\ell^2}\right)^{2^\ell}, \end{equation*}

as required.

Proof of Lemma 2.2. Let $G=(V,E)$ be a graph on n vertices with minimal degree at least $\delta n$ , let $\varepsilon>0$ and let $0 < \beta\leq 240n^2/(\varepsilon\delta^4)$ . By Lemma 2.11, there exists a $\delta$ -primary decomposition of V. We denote this decomposition by $\mathcal{P}'$ . By Lemma 2.13, we obtain that there exists an $(\varepsilon,\varepsilon^9,\beta)$ -good coarsening of $\mathcal{P}'$ , denoted by $\mathcal{P}$ . We also denote this coarsening explicitly by $V=V_1 \sqcup \ldots \sqcup V_k$ and we let $\theta$ be the parameter from Lemma 2.13 to which the coarsening corresponds.

We claim that $\mathcal{P}$ is indeed an $(\varepsilon,\delta,\beta)$ -good decomposition satisfying conditions (3) and (5) of Definition 2.1 with this $\theta$ . We first note that for $\varepsilon>0$ small enough and by the properties of a good coarsening

\begin{equation*} \varepsilon^{11\cdot 2^{2/\delta}} \leq \varepsilon\left(\frac{\varepsilon^{10}\delta^2}{4}\right)^{2^{2/\delta}} \leq \theta \leq \varepsilon. \end{equation*}

Conditions (1), (2) and (4) of Definition 2.1 are immediate for every coarsening of a $\delta$ -primary decomposition. Condition (5) is satisfied by condition (2) of the coarsening in Definition 2.12. We are then left with verifying that condition (3) of Definition 2.1 holds. To this end, we let $V_i$ be some set in $\mathcal{P}$ and $V_i = V_{i,1}\sqcup\ldots\sqcup V_{i,\ell_i}$ be its partition to $\ell_i$ sets of $\mathcal{P}'$ which we denote by $\mathcal{P}_i$ . Note that for every $j\in[\ell_i]$ and for every $v\in V_{i,j}$ we have $\deg\!(v,V_{i,j}) \geq \delta^4n/40$ . Also, by condition (4) of the primary decomposition, Definition 2.10, we have that the spectral gap corresponding to $G[V_{i,j}]$ is at least $\delta^{10}/2^{22}$ . Finally, by the properties of the coarsening, the graph $H(\mathcal{P}_i, \theta \beta)$ is connected. Hence, denoting $\gamma(G[V_i])$ for the spectral gap of $G[V_i]$ and using Lemma 2.4 we get that

(9) \begin{equation} \gamma(G[V_i]) \geq \min\left\{\frac{\delta^{10}}{2^{22}},\quad \frac{\delta^4 n}{40}\cdot\frac{\delta^{10}}{2^{22}}\cdot\theta \beta\cdot\frac{1}{6\ell_in^3}\right\}. \end{equation}

Since $\theta \leq \varepsilon$ and $\beta\leq 240n^2/(\varepsilon\delta^4)$ and $\ell_i \geq 1$ we learn that the minimum above is attained in the second term. As $\mathcal{P}$ is a coarsening of a $\delta$ -primary decomposition, we have that $\ell_i\leq 2/\delta$ , hence,

\begin{equation*} \gamma(G[V_i]) \geq \frac{\delta^4 n}{40}\cdot\frac{\delta^{10}}{2^{22}}\cdot\theta \beta\cdot\frac{1}{6\ell_in^3} \geq \frac{\delta^{15}\theta\beta}{2^{31}n^2} \end{equation*}

and we deduce that condition (3) of Definition 2.1 holds.

Proof Let P be the transition matrix of the lazy random walk on G. Recall that P is a self-adjoint operator $P\,{:}\,L^2(\pi)\to L^2(\pi)$ where $\pi(v)=\deg_G\!(v)/2|E(G)|$ is the stationary distribution. We denote the eigenvalues of P by $1 = \lambda_1 \geq \ldots \geq \lambda_n\geq 0$ and $\gamma(P) = 1-\lambda_2$ and by ${\textbf{1}}$ the all 1 vector which is the eigenvalue corresponding to the eigenvalue 1. Let $\mu$ be any probability measure on V and write f for the vector $f(v)=\mu(v)/\pi(v)$ . We have that $f-{\textbf{1}}$ is orthogonal to ${\textbf{1}}$ and for any integer $t\geq 1$ we have that $\pi(v) Pf(v) = \mathbb{P}_\mu(X_t = \cdot)$ so in particular $P^t f - {\textbf{1}}$ is orthogonal to ${\textbf{1}}.$ Hence

(10) \begin{equation} \left\| P^t f - {\textbf{1}} \right\|_2 = \left\| P^t\left(f - {\textbf{1}}\right) \right\|_2 \leq \lambda_2^t\left\|f - {\textbf{1}} \right\|_2 .\end{equation}

We rewrite this as

\begin{equation*} \left\| \frac{\mathbb{P}_\mu(X_t = \cdot)}{\pi(\cdot)} - {\textbf{1}} \right\|_2 \leq \lambda_2^t \left\|f - {\textbf{1}} \right\|_2. \end{equation*}

We now claim that for any $v\in V$ and every $u\in V$ we have that

\begin{equation*} \mathbb{P}_v(X_{\left\lceil{\log_2\!(n)}\right\rceil} = u) \leq \frac{2}{\delta n}. \end{equation*}

Indeed, if the random walker made a non-lazy step at some time in $\{1, \ldots, \left\lceil{\log_2\!(n)}\right\rceil\}$ , then the probability to be at any vertex u at time $\left\lceil{\log_2\!(n)}\right\rceil$ is bounded by $1/(\delta n)$ . On the other hand, the probability of staying put $\left\lceil{\log_2\!(n)}\right\rceil$ steps is at most ${1 \over n}$ . Since ${\delta \over n} \leq \pi(\cdot) \leq {1 \over \delta n}$ it follows that

(11) \begin{equation} \left\| \frac{\mathbb{P}_v(X_{\left\lceil{\log_2\!(n)}\right\rceil} = \cdot)}{\pi(\cdot)} - {\textbf{1}} \right\|_2^2 \leq \frac{2}{\delta^2}. \end{equation}

Using (10) and (11), for $t = \left\lceil{\log_2\!(n)}\right\rceil + \log(\sqrt{2}/\varepsilon \delta)\gamma^{-1}$ and every $v\in V$ we have

\begin{equation*} \left\| \frac{\mathbb{P}_v(X_t = \cdot)}{\pi(\cdot)} - {\textbf{1}} \right\|_2 \leq \lambda_2^{t-\left\lceil{\log_2\!(n)}\right\rceil}\left\| \frac{\mathbb{P}_v(X_{\left\lceil{\log_2\!(n)}\right\rceil} = \cdot)}{\pi(\cdot)} - 1 \right\|_2 \leq \frac{\sqrt{2}}{\delta}(1-\gamma)^{t-\left\lceil{\log_2\!(n)}\right\rceil} \leq \varepsilon. \end{equation*}

By [Reference Levin and Peres14, Lemma 12.18] we have that

\begin{equation*} 2\|\textbf{p}_t(v,\cdot) - \pi(\cdot)\|_{{d_{\textrm{TV}}}} \leq \left\| \frac{\mathbb{P}_v(X_t = \cdot)}{\pi(\cdot)} - 1 \right\|_2 \leq \varepsilon \, , \end{equation*}

concluding our proof.

Proof. We prove this for the lazy simple random walk and trivially it follows for the usual random walk. Without loss of generality we may assume that $|U|=\left\lceil{\varepsilon \sqrt{n}}\right\rceil$ , otherwise we may take a subset of U of that size. By equation (3) we have that $2({t_{\textrm{mix}}^G}(\varepsilon/2) + \left\lfloor{\sqrt{n}}\right\rfloor) \geq {t_{\textrm{mix}}^G}(\varepsilon^2) + \left\lfloor{\sqrt{n}}\right\rfloor$ so it is then enough to bound from below the probability that X hits U within ${t_{\textrm{mix}}^G}(\varepsilon^2) + \left\lfloor{\sqrt{n}}\right\rfloor$ steps. Recall that

(12) \begin{equation} \mathbb{P}(Z>0) \geq \frac{{\mathbb{E}}^2[Z]}{{\mathbb{E}}[Z^2]} \, , \end{equation}

for any non-negative random variable Z. Let Y be a lazy random walk starting from the stationary distribution and define $Z = |\{t\in[0,\left\lfloor{\sqrt{n}}\right\rfloor] \mid Y_t\in U\}|$ . We will use (12) to bound $\mathbb{P}(Z>0)$ from below. Since $|U|\geq\varepsilon\sqrt{n}$ and the minimal degree is $\delta n$ , we have that $\pi(U) \geq \varepsilon \delta n^{-1/2}$ and so ${\mathbb{E}}[Z] = (\left\lfloor{\sqrt{n}}\right\rfloor+1) \pi(U) \geq \varepsilon\delta$ .

To bound ${\mathbb{E}}[Z^2]$ , let $t<r$ be two positive integers. If $Y_t \in U$ , there is a probability of $2^{-(r-t)}$ that the walker made $r-t$ lazy steps and then $Y_r = Y_t$ . Else, since the minimal degree is at least $\delta n$ , the probability that $Y_r \in U$ is bounded by $|U|/(\delta n)$ . Therefore,

\begin{equation*} \mathbb{P}(Y_t \in U, Y_r \in U) \leq \mathbb{P}(Y_t \in U)\cdot\left(\frac{|U|}{\delta n} + \frac{1}{2^{r-t}}\right) = \pi(U) \cdot\left(\frac{|U|}{\delta n} + \frac{1}{2^{r-t}}\right). \end{equation*}

Hence, by summing over all $t\leq r\leq\left\lfloor{\sqrt{n}}\right\rfloor$

\begin{align*} {\mathbb{E}}[Z^2] &= \sum_{t=0}^{\left\lfloor{\sqrt{n}}\right\rfloor} \mathbb{P}(Y_t\in U) + 2\sum_{t=0}^{\left\lfloor{\sqrt{n}}\right\rfloor}\sum_{r=t+1}^{\left\lfloor{\sqrt{n}}\right\rfloor} \mathbb{P}(Y_t\in U, Y_r\in U) \\&\leq {\mathbb{E}}[Z] + 2\binom{\left\lfloor{\sqrt{n}}\right\rfloor+1}{2}\frac{\pi(U)|U|}{\delta n} + 2\sum_{t=0}^{\left\lfloor{\sqrt{n}}\right\rfloor}\pi(U)\sum_{r=t+1}^{\left\lfloor{\sqrt{n}}\right\rfloor}\frac{1}{2^{r-t}}. \end{align*}

Since ${\mathbb{E}}[Z] = \left(\left\lfloor{\sqrt{n}}\right\rfloor+1\right)\pi(U)$ we upper bound the last term of the right-hand side by $2{\mathbb{E}}[Z]$ . For the middle term we write

\begin{align*} 2\binom{\left\lfloor{\sqrt{n}}\right\rfloor+1}{2}\frac{\pi(U)|U|}{\delta n} \leq (\left\lfloor{\sqrt{n}}\right\rfloor + 1)\cdot\frac{\pi(U)|U|}{\delta \sqrt{n}}\leq {\mathbb{E}}[Z]\left(\frac{\varepsilon\sqrt{n} +1}{\delta\sqrt{n}}\right)\leq \frac{1}{2}{\mathbb{E}}[Z], \end{align*}

where the last inequality holds for $\varepsilon$ small enough. Therefore, for $\varepsilon$ small enough we have that ${\mathbb{E}}[Z^2] \leq \frac{7}{2}{\mathbb{E}}[Z]$ and thus by (12)

\begin{equation*} \mathbb{P}(Z>0) \geq \frac{2{\mathbb{E}}[Z]}{7} \geq \frac{2\varepsilon\delta}{7}. \end{equation*}

By the definition of ${t_{\textrm{mix}}^G}(\varepsilon^2)$ , if X is a random walk starting from some $v\in V$ , we have that ${d_{\textrm{TV}}}(X_{{t_{\textrm{mix}}}(\varepsilon^2)},\pi) \leq \varepsilon^2$ . Therefore, we can couple the walk X starting from time ${t_{\textrm{mix}}^G}(\varepsilon^2)$ with an independent random walk Y starting from the stationary distribution such that the walks coincide with probability larger than $1-\varepsilon^2$ . We thus obtain that for $\varepsilon$ small enough

\begin{equation*} \mathbb{P}_v(X[{t_{\textrm{mix}}^G}(\varepsilon^2), {t_{\textrm{mix}}^G}(\varepsilon^2)+\left\lfloor{\sqrt{n}}\right\rfloor]\cap U \neq \varnothing) \geq \varepsilon\delta/3.5 - \varepsilon^2 \geq \varepsilon\delta/4. \end{equation*}

Proof. Let $i\in[k]$ and let $\theta$ be the parameter from the $(\varepsilon,\delta,n^{1.5})$ -good decomposition $\mathcal{P}$ . For every $t\geq 1$ , we have

\begin{equation*} \mathbb{P}(X_t \in V_i, X_{t+1}\not \in V_i) \leq \sum_{w\in V_i} \mathbb{P}(X_t = w)\cdot \textbf{p}(w,V_i^c) \leq \sum_{w\in V_i}\frac{1}{\delta n}\frac{|E(w,V_i^c)|}{\delta n} = \frac{|E(V_i,V_i^c)|}{\delta^2 n^2} \, . \end{equation*}

Hence by taking the union over $t\in[1,C\sqrt{n}]$ and using condition (5) of a $(\varepsilon,\delta,n^{1.5})$ -good decomposition (Definition 2.1) we immediately obtain (13). To prove (14) let $C>0$ and fix some $v\in V_i$ . By condition (4) of Definition 2.1, we have that $\deg\!(v,V_i) \geq \delta^4n/40$ . By (13) we have

\begin{equation*} \mathbb{P}_v(X_1\in V_i \ \textrm{and} \ X\left[1,C\sqrt{n} + 1\right] \not\subseteq V_i) \leq \frac{C\theta^2\varepsilon^9}{\delta^2}. \end{equation*}

Yet on the other hand,

\begin{align*} &\mathbb{P}_v(X_1 \in V_i \ \textrm{and} \ X[1,C\sqrt{n}] \not\subseteq V_i) \geq \frac{1}{n} \sum_{u\sim v, u\in V_i} \mathbb{P}_u\!\left(X[0,C\sqrt{n}] \not\subseteq V_i\right). \end{align*}

Thus the number of $u \in V_i$ with $u\sim v$ satisfying

\begin{equation*} \mathbb{P}_u\left(X[0,C\sqrt{n}] \not\subseteq V_i\right) \geq \frac{80C\theta^2\varepsilon^9}{\delta^6}.\end{equation*}

cannot be larger than $\delta^4n/80$ . Since $\deg\!(v,V_i) \geq \delta^4n/40$ we conclude the proof of (14).

Proof. Apply Lemma 3.5 with $C=1/\theta\varepsilon^6$ to obtain a set $V'_i$ such that for every $v\in V_i'$ , if Y is a simple random walk on the graph G, then

(16) \begin{equation} \mathbb{P}_v(Y[0,\sqrt{n}/\theta\varepsilon^6] \subseteq V_i) \geq 1-\frac{80\theta\varepsilon^3}{\delta^6} \geq 1-B\varepsilon^3. \end{equation}

Also, for a random walk X on $G^\rho$ we have ${\mathbb{E}}_v \tau_\rho = \sqrt{n}/\theta\varepsilon^{4}$ and thus Markov’s inequality gives

(17) \begin{equation} \mathbb{P}_v(\tau_\rho \leq \sqrt{n}/\theta\varepsilon^{6})\geq 1-\varepsilon^2 \end{equation}

Let X be a random walk on $G^\rho$ . Conditioned on $\tau_\rho$ the random path $X[0,\tau_\rho-1]$ has the distribution of a random walk on G. Hence combining (16) and (17) yields the desired result.

Proof. As in the previous proof, for every $v\in V_i$ we have that $\mathbb{P}(\tau_{\rho} > \sqrt{n}) \geq 1-\varepsilon^4$ . We condition on this event on $\tau_\rho$ and on the first $\tau_\rho - \varepsilon \sqrt{n}$ steps of the random walk. Let us assume first that

\begin{equation*} |{\mathsf{LE}}(X[0,\tau_{\rho} - \varepsilon\sqrt{n}))| \geq \varepsilon\sqrt{n}. \end{equation*}

In this case we denote by U the first $\varepsilon \sqrt{n}$ vertices of ${\mathsf{LE}}(X[0,\tau_{\rho} - \varepsilon\sqrt{n}))$ . As before, conditioned on $\tau_\rho$ the walk $X[0,\tau_\rho-1]$ is distributed as an unconditional random walk. By the Markov property, the random walk at times $[\tau_{\rho} - \varepsilon\sqrt{n},\tau_{\rho})$ is distributed as an unconditional random walk on the graph G. Hence, since the minimal degree of G is at least $\delta n$ , the probability that $X_t\in U$ for some $t\in [\tau_{\rho} - \varepsilon\sqrt{n},\tau_{\rho}]$ is at most $\varepsilon^2/\delta$ . If this does not occur, then the set U survives the loop erasure. It follows that

\begin{equation*} \mathbb{P}\left( |{\mathsf{LE}}\left(X[0,\tau_{\rho} - \varepsilon\sqrt{n}] \right)| \geq \varepsilon\sqrt{n} \ \textrm{and} \ |{\mathsf{LE}}(X)| \leq \varepsilon\sqrt{n} \right) \leq \varepsilon^4 + \varepsilon^2/\delta \leq C\varepsilon^2 , \end{equation*}

for some $C=1+\delta^{-1}$ . In the second case $|{\mathsf{LE}}(X[0,\tau_{\rho} - \varepsilon\sqrt{n}))| \leq \varepsilon\sqrt{n}$ . In this case the last $\varepsilon\sqrt{n}$ steps of X will survive the loop erasure high probability. Indeed, by Markov’s inequality and since the degrees are at least $\delta n$ we deduce that the walk $X[\tau_{\rho} - \varepsilon\sqrt{n},\tau_{\rho}]$ has no loops with probability at least $1-\varepsilon^2/\delta$ . By the same reasoning, the walk $X[\tau_{\rho} - \varepsilon\sqrt{n},\tau_{\rho}]$ does not visit $|{\mathsf{LE}}(X[0,\tau_{\rho} - \varepsilon\sqrt{n}))|$ with probability at least $1-\varepsilon^2/\delta$ . On these two events ${\mathsf{LE}}(X)$ contains $X[\tau_{\rho} - \varepsilon\sqrt{n},\tau_{\rho}]$ . It follows that

\begin{equation*} \mathbb{P}( |{\mathsf{LE}}(X[0,\tau_{\rho} - \varepsilon\sqrt{n}))| \leq \varepsilon\sqrt{n} \ \textrm{and} \ |{\mathsf{LE}}(X)| \leq \varepsilon\sqrt{n} ) \leq \varepsilon^4 + 2\varepsilon^2/\delta \leq C\varepsilon^2 , \end{equation*}

for some $C=1+2\delta^{-1}$ . Combining the last two inequalities and using Claim 3.6 finishes the proof.

Proof. We apply Claim 3.7 to obtain the set $V_i'$ and take $v_1,v_2$ to be any two distinct vertices of $V_i'$ . Let Z be simple random walk on $G[V_i]$ starting at $v_2$ independent of X (note that unlike Y, the random walk Z does not leave $V_i$ and does not visit $\rho$ ). By Lemma 3.2 and condition (3) of an $(\varepsilon,\delta,n^{1.5})$ -good decomposition (Definition 2.1) we have that for some $C=C(\delta)$

\begin{equation*} {t_{\textrm{mix}}^{G[V_i]}}(\varepsilon/2)+\left\lfloor{\sqrt{n}}\right\rfloor \leq C\log(1/\varepsilon)\frac{\sqrt{n}}{\theta}. \end{equation*}

Fix a constant

\begin{equation*}A = \left\lceil{320\log\!(1/\varepsilon)/\varepsilon\delta^4}\right\rceil ,\end{equation*}

so that by the last estimate, and since $v_2 \in V_i'$ the assertion of Lemma 3.5 implies that

(19) \begin{align} \mathbb{P}_{v_2}\left(Y\left[0,2A({t_{\textrm{mix}}^{G[V_i]}}(\varepsilon/2)+\left\lfloor{\sqrt{n}}\right\rfloor)\right] \subseteq V_i\right) &\geq \mathbb{P}_{v_2}\left(Y\left[0,\frac{2AC\log(1/\varepsilon)\sqrt{n}}{\theta}\right] \subseteq V_i\right)\nonumber \\&\geq 1-\frac{160AC\theta\varepsilon^8}{\delta^6} - \mathbb{P}\left(\tau_{\rho} \leq \frac{2AC\log(1/\varepsilon)\sqrt{n}}{\theta}\right) \nonumber\\&\geq 1 - C\varepsilon^2, \end{align}

for some $C = C(\delta)$ . Thus we learn that with probability larger than $1-C\varepsilon^2$ we can couple Y and Z such that $Y_t = Z_t$ for all $t\leq 2A({t_{\textrm{mix}}^{G[V_i]}}(\varepsilon/2)+\left\lfloor{\sqrt{n}}\right\rfloor)$ . Now, since $v_1\in V_i'$ the assertion of Claim 3.7 states that with probability at least $1-C\varepsilon^2$ we have that $|{\mathsf{LE}}(X)|\geq \varepsilon \sqrt{n}$ and ${\mathsf{LE}}(X)\subseteq V_i \cup \{\rho\}$ . The minimal degree in $G[V_i]$ is at least $\delta^4n /40$ and $\delta n /2 \leq |V_i|\leq n$ , allowing us to apply Claim 3.3 A times together with the previous estimate to obtain that

\begin{equation*} \mathbb{P}_{v_2}(Z[0,2A({t_{\textrm{mix}}^{G[V_i]}}(\varepsilon/2)+\left\lfloor{\sqrt{n}}\right\rfloor)] \cap {\mathsf{LE}}(X) = \varnothing) \leq \left(1-\frac{\varepsilon\delta^4}{160}\right)^A + C\varepsilon^2 \leq (C+1) \varepsilon^2 , \end{equation*}

by our choice of A. This together with the coupling of Y and Z and (19) gives

\begin{equation*} \mathbb{P}\left(Y_{\tau_{{\mathsf{LE}}(X)}} \neq \rho \ \textrm{and} \ {\mathsf{LE}}(Y) \subset V_i \right) \geq 1-C\varepsilon^2. \end{equation*}

We are left with bounding $|{\mathsf{LE}}(Y)|$ from below. We will show that with large probability $Y[0,\varepsilon^8\theta\sqrt{n})\subseteq {\mathsf{LE}}(Y)$ . Indeed, since ${\mathbb{E}}_{v_1} \tau_\rho=\sqrt{n}/\theta\varepsilon^{4}$ we have that $|{\mathsf{LE}}(X)|\leq \sqrt{n}/\theta\varepsilon^6$ with probability at least $1-\varepsilon^2$ . Furthermore, since $v_1\neq v_2$ and the degree is at least $\delta n$ we have that $v_2\not \in {\mathsf{LE}}(X)$ with probability at least $1-\varepsilon^2-\delta^{-1}n^{-1/2}/\theta \varepsilon^6 \geq 1-C\varepsilon^2$ . Hence

(20) \begin{align} \mathbb{P}(Y[0,\varepsilon^8\theta\sqrt{n}) \cap {\mathsf{LE}}(X) \neq \varnothing) &\leq \varepsilon^8\theta\sqrt{n} \frac{\sqrt{n}/\theta \varepsilon^6}{\delta n} + C\varepsilon^2 \leq C\varepsilon^2. \end{align}

Furthermore, since the degree is at least $\delta n$ , the union bound gives that

(21) \begin{equation} \mathbb{P}(Y[0,\varepsilon^{8}\theta\sqrt{n}) \cap Y[\varepsilon^{8}\theta\sqrt{n}, \sqrt{n}/\theta\varepsilon^{6}) \neq\varnothing ) \leq \frac{\varepsilon^2}{\delta}. \end{equation}

Since $\tau_\rho \geq \sqrt{n}/\theta \varepsilon^6$ occurs with probability at most $\varepsilon^2$ , we deduce by (20), (21) that

\begin{equation*} \mathbb{P}\left( {\mathsf{LE}}(Y[0,\varepsilon^{8}\theta\sqrt{n})) \subseteq {\mathsf{LE}}(Y)\right) \geq 1 - C\varepsilon^2. \end{equation*}

for some $C=C(\delta)<\infty$ . Lastly, again by the linear minimal degree and the union bound, the probability that there is a repeating vertex in $Y[0,\varepsilon^{8}\theta\sqrt{n})$ is at most $\varepsilon^{16}\theta^2/\delta$ ; when this does not occur $Y[0,\varepsilon^{8}\theta\sqrt{n})={\mathsf{LE}}(Y[0,\varepsilon^{8}\theta\sqrt{n}))$ , concluding our proof.

Proof of Lemma 3.1. If $\theta\varepsilon^8 \leq 1 / \sqrt{n}$ , the claim is trivial. We assume the converse is true, and we take the vertices $v_1^i$ and $v_2^i$ from Lemma 3.8. We denote by $\varphi$ and $\varphi'$ the paths between them in $\mathsf{UST}(G)$ and $\mathsf{UST}(G^\rho)$ , respectively. As mentioned in the beginning of this subsection, we couple $\mathsf{UST}(G)$ and $\mathsf{UST}(G^\rho)$ such that $\mathsf{UST}(G^\rho)\cap E(G)\subseteq\mathsf{UST}(G)$ . We use (15) and recall that under this coupling, if $\rho\notin \varphi'$ , then $\varphi=\varphi'$ . Hence it suffices to show that

\begin{equation*} \mathbb{P}\left(\varepsilon^8\theta\sqrt{n} \leq |\varphi'| \leq \frac{\sqrt{n}}{\theta\varepsilon^{8}} \ \textrm{and} \ \varphi' \subseteq V_i \ \textrm{and} \ \rho\notin\varphi' \right) \geq 1-C\varepsilon^2, \end{equation*}

for some $C = C(\delta)$ . By Wilson’s algorithm, we can sample $\varphi'$ by sampling ${\mathsf{LE}}(X)$ , a ${\mathsf{LERW}}$ from $v_1^i$ to $\rho$ and then sampling ${\mathsf{LE}}(Y)$ , another ${\mathsf{LERW}}$ from $v_2^i$ to ${\mathsf{LE}}(X)$ . The path between $v_1^i$ and $v_2^i$ in ${\mathsf{LE}}(X)\cup{\mathsf{LE}}(Y)$ is distributed as the path between $v_1^i$ and $v_2^i$ in $\mathsf{UST}(G^\rho)$ . By Lemma 3.8 and Claim 3.7, this path is contained in $V_i$ and does not contain $\rho$ with probability larger than $1-C\varepsilon^2$ . By construction $|\varphi'|\geq |{\mathsf{LE}}(Y)|$ hence Lemma 3.8 gives the required lower bound on $|\varphi'|$ . Finally, as the length of ${\mathsf{LE}}(X)$ and ${\mathsf{LE}}(Y)$ is bounded by two independent random variables with the distribution of $\tau_{\rho}$ , by Markov’s inequality

\begin{equation*} \mathbb{P}\left(|{\mathsf{LE}}(X)| + |{\mathsf{LE}}(Y)| \geq \frac{\sqrt{n}}{\theta\varepsilon^8}\right) \leq 1-C\varepsilon^4, \end{equation*}

concluding the proof.