Proof. Let \(G=(V,E)\). By Lemma [lem:phase195bdd], there is a constant \(C_1 \in (0,1)\) such that, with probability \(1-o_n(1)\) over the choice of \(G\), for all \(u \in V\) and \(\eta \in \{0, 1\}^E\), \[\label{eq:main1} \mathbb{P}\left[X_{T_1} \in V_{\mathrm{good}}\mid \left(\eta_0, X_0\right) = \left(\eta, u\right)\right] \geq C_1.\tag{1}\] By Lemma [lem:phase295bdd] there is a constant \(C_2\in (0,1)\) such that, with probability \(1-o_n(1)\), for all \(v \in V_{\mathrm{good}}\) there is a set \(S_v \subseteq V\) such that \(|S_v| = n - o(n)\) and for all \(x \in S_v\) and \(\hat{\eta} \in \{0, 1\}^E\), \[\label{eq:main2} \mathbb{P}\left[X_{T_2} = x \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \geq {C_2}/{n}.\tag{2}\]

Blanca and Gheissari established in [1] that, with probability \(1-o_n(1)\) over the choice of \(G\), the mixing time of the discrete-time random cluster Glauber dynamics with parameters \((p, q)\) on \(G\) satisfies \(t_{\mathrm{mix}}^{\mathrm{GD}, (p, q)} (G) = \Theta(n \log n)\). This gives a \(\Theta(\log n)\) mixing time in continuous time, and a \(\Theta(1)\) mixing time in our setting with \(\mu \geq \epsilon \log n\). Consequently, there is a constant \(\tau > 0\) such that, with probability \(1 - o_n(1)\) over the choice of \(G\), for every \(\mu \geq \varepsilon \log n\) and every initial distribution \(\eta_0 \sim \rho\), the law of the environment dynamics \((\eta_t^{(\rho)})_{t \geq 0}\) at time \(\tau\) is within total variation distance \(1/8\) of \(\pi_{G, p, q}\).

Let \(T_3 \mathrel{\vcenter{:}}= T_2 + \tau\). Given \(v, x \in V\) and \(\hat{\eta} \in \{0, 1\}^E\), let \(\rho \mathrel{\vcenter{:}}= \rho\left(\hat{\eta}, v, x\right)\) be the law of \(\eta_{T_2}\) conditioned on \((\eta_{T_1}, X_{T_1}) = (\hat{\eta}, v)\) and \(X_{T_2} = x\). Let \[F_{\hat{\eta}, v, x} \! \mathrel{\vcenter{:}}= \! \left\{\omega \in \{0, 1\}^E \colon \mathbb{P}\left[\eta_{T_3} = \omega \mid \eta_{T_2} \sim \rho\left(\hat{\eta}, v, x\right)\right] \geq (1/2) \pi_{G, p, q}(\omega)\right\}.\] For all \(\omega\in \{0,1\}^E\setminus F_{\hat{\eta},v,x}\), \(\min\{\mathbb{P}\left[\eta_{T_3} = \omega \mid \eta_{T_2} \sim \rho(\hat{\eta}, v, x)\right], \pi_{G, p, q}(\omega)\}\) is at most \((1/2)\pi_{G,p,q}(\omega)\) and for \(\omega\in F_{\hat{\eta},v,x}\) this quantity is at most \(\pi_{G,p,q}(\omega)\). Let \(\mathcal{D}(\eta^{(\rho)}_{\tau})\) be the distribution of the environment dynamics, started from the initial distribution \(\rho\), at time \(\tau\). Since \(||\mathcal{D}(\eta^{(\rho)}_{\tau}) - \pi_{G, p, q}||_{\mathrm{TV}} \leq 1/8\) for our choice of \(\tau\), and since \(||\mathcal{D}(\eta^{(\rho)}_{\tau}) - \pi_{G, p, q}||_{\mathrm{TV}} \! = 1 - \!\!\!\!\!\! \sum\limits_{\omega \in \{0, 1\}^E} \!\!\!\!\!\! \min\left\{\mathbb{P}\left[\eta_{T_3} = \omega \mid \eta_{T_2} \sim \rho\right], \pi_{G, p, q}(\omega)\right\}\), we have that \(\pi_{G, p, q} \left(F_{\hat{\eta}, v, x}\right) \geq 3/4\). Since the environment evolves independently of the walker, if the walker clock does not ring between \(T_2\) and \(T_3\), the walker remains at the same vertex while the environment mixes. Thus, for all \(v, x \in V\), \(\hat{\eta} \in \{0, 1\}^E\) and \(\omega \in F_{\hat{\eta}, v, x}\), \[\begin{align} &\;\mathbb{P}\left[\left(\eta_{T_3}, X_{T_3}\right) = (\omega, x) \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \\ \geq& \;\mathbb{P}\left[\eta_{T_3} = \omega, N_{\mathrm{w}}(T_2, T_3) = 0 \mid X_{T_2} = x, \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \mathbb{P}\left[X_{T_2} = x \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \\ =& \;\mathbb{P}\left[N_{\mathrm{w}}(T_2, T_3) = 0\right]\mathbb{P}\left[\eta_{T_3} = \omega \mid X_{T_2} = x, \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \mathbb{P}\left[X_{T_2} = x \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \\ \geq& \;(1/2) e^{-\tau} \pi_{G, p, q}(\omega) \mathbb{P}\left[X_{T_2} = x \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \end{align}\] where the last inequality follows from the fact that \(\omega \in F_{\hat{\eta}, v,x}\) and the fact that the probability of a clock of rate \(1\) not ringing in \(\tau\) time is \(e^{-\tau}\). Combining this with (2 ), we get that for all \(v \in V_{\mathrm{good}}\) there is a set \(S_v \subseteq V\) satisfying \(|S_v| = n - o(n)\) such that, for all \(\left(\hat{\eta}, x\right) \in \{0, 1\}^E \times S_v\) and \(\omega \in F_{\hat{\eta}, v, x}\), \[\label{eq:main4} \mathbb{P}\left[\left(\eta_{T_3}, X_{T_3}\right) = (\omega, x) \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \geq \left(\frac{C_2 e^{-\tau}}{2 n}\right) \pi_{G, p, q}(\omega).\tag{3}\]

Under a maximal coupling from time \(T_1\) to time \(T_3\), from (3 ) and from the fact that \(\pi_V(x) = 1/n\), we have that \[\begin{align} &\;\mathbb{P}\left[\left(\eta_{T_3}, X_{T_3}\right) = \left(\eta'_{T_3}, X'_{T_3}\right) \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right]\\ =&\;\sum_{(\omega, x) \in \{0, 1\}^E \times V} \min\left\{\mathbb{P}\left[\left(\eta_{T_3}, X_{T_3}\right) = (\omega, x) \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right], \pi_{G, p, q} (\omega) \pi_V (x)\right\} \\ \geq& \sum_{x \in S_v} \sum_{\omega \in F_{\hat{\eta},v,x}} \min \{\frac{C_2 e^{-\tau}}{2 n} \pi_{G,p,q}(\omega), \pi_{G,p,q}(\omega) (1/n)\} \geq \;\frac{C_2 e^{-\tau}}{2 n} \sum_{x \in S_v} \pi_{G, p, q} \left(F_{\hat{\eta}, v, x}\right). \end{align}\] Since \(|S_v| = n - o(n)\) and \(\pi_{G, p, q} (F_{\hat{\eta}, v, x}) \geq \frac{3}{4}\) for all \(x\), this is at least \(3 C_2 e^{-\tau}({n - o(n)})/(8n) \geq {C_2 e^{-\tau}}/{8}\). Therefore, the probability of coupling at time \(T_3\) is \[\begin{align} & \;\mathbb{P}\left[\left(\eta_{T_3}, X_{T_3}\right) = \left(\eta'_{T_3}, X'_{T_3}\right) \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \\ \geq& \;\sum_{v \in V_{\mathrm{good}}} \sum_{\hat{\eta} \in \{0, 1\}^E} \mathbb{P}\left[\left(\eta_{T_3}, X_{T_3}\right) = \left(\eta'_{T_3}, X'_{T_3}\right), \left(\eta_{T_1}, X_{T_1}\right) = (\hat{\eta}, v) \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \\ \geq& \;\sum_{v \in V_{\mathrm{good}}} \sum_{\hat{\eta} \in \{0, 1\}^E} \frac{C_2 e^{-\tau}}{8} \;\mathbb{P} \left[\left(\eta_{T_1}, X_{T_1}\right) = (\hat{\eta}, v) \mid \left(\eta_0, X_0\right) = (\eta, u) \right] \\ =& \;\sum_{v \in V_{\mathrm{good}}} \frac{C_2 e^{-\tau}}{8} \;\mathbb{P} \left[X_{T_1} = v \mid \left(\eta_0, X_0\right) = (\eta, u) \right] \\ =& \;\frac{C_2 e^{-\tau}}{8} \;\mathbb{P} \left[X_{T_1} \in V_{\mathrm{good}}\mid \left(\eta_0, X_0\right) = (\eta, u) \right] \geq \frac{C_1 C_2 e^{-\tau}}{8} \end{align}\] where the last inequality follows from (1 ). Hence, with probability \(\Omega(1)\), the two chains couple at time \(T_3\) and therefore the mixing time is \(O(\log n)\). ◻

Proof. Let \(\alpha_{\max}\mathrel{\vcenter{:}}= \lfloor ({4}/{p_{\min}}) \log_{d - 1} n\rfloor\) and \(T_{\mathrm{max}}\mathrel{\vcenter{:}}= ({4}/{p_{\min}}) \log_{d - 1} n\). By Lemma 2, with probability \(1 - O\left(n^{-1}\right)\) over \(G \sim \mathcal{G}(d, n)\), for all \(\mu \geq \varepsilon \log n\), for all \(t' > t \geq C_{\mathrm{burn}}\) such that \(t' - t \leq T_{\mathrm{max}}\) and for all \((\eta, v) \in \{0, 1\}^E \times V\), \[\label{eq:wtp1} \mathbb{P} \left[\neg S_{[t' - \Delta, t']} (R, K) \mid (\eta_0, X_0) = (\eta, v)\right] = O\left(\tfrac{1}{n} \left(\tfrac{p_{\min}}{4 d}\right)^{\alpha_{\max}}\right)\tag{4}\] where \(\Delta \mathrel{\vcenter{:}}= (t' - t) \left(\frac{\varepsilon \log n}{\mu}\right)\), noting that the environment dynamics evolve independently of the walker history. Furthermore, by Lemma 2.1 in [7], we have that, with probability \(1 - o_n(1)\) over \(G \sim \mathcal{G}(d, n)\), every radius-\(R\) ball in \(G\) contains at most one cycle.

Hence, with probability \(1 - o_n(1)\) over \(G \sim \mathcal{G}(d, n)\), both of these properties hold. Fix such a graph \(G\). Fix \(\eta \in \{0, 1\}^E\), \(\mu \geq \varepsilon \log n\), \(T > 0\) such that \(({1}/{(50 \;p_{\min})}) \log_{d - 1} n \leq T \leq T_{\mathrm{max}}\), \(\alpha \in \mathbb{N}\) such that \(\alpha \leq \alpha_{\max}\), and let \(\overrightarrow{x_\alpha} = (x_0, \dots, x_\alpha) \in V^{\alpha + 1}\) be an \(r\)-acyclic walk.

Let \(\mathcal{N}_0\) and \(\mathcal{N}_\alpha\) denote the events \(N_\mathrm{w}[0, C_{\mathrm{burn}}] = 0\) and \(N_\mathrm{w}(C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) = \alpha\), respectively. These events are independent since they concern the ringing of the same Poisson clock over disjoint time intervals. Conditioned on the event \(\mathcal{N}_0\), the walker does not move during \([0, C_{\mathrm{burn}}]\), and hence \(X_{C_{\mathrm{burn}}} = x_0\). If, furthermore, the event \(\mathcal{N}_\alpha\) holds and the \(\alpha\) ordered ring times of \(\mathsf{C}_{\mathrm{w}}\) in \((C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T)\) are given by the vector \(\overrightarrow{\tau_\alpha}\), then the event \(\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{\tau_\alpha}\right)\) forces the walker to follow the trajectory \(\overrightarrow{x_\alpha}\) during \((C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T)\) such that \(X_{C_{\mathrm{burn}}+ T} = x_\alpha\). Therefore these events imply \(\widehat\Xi \left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right)\).

Conditioned on \(\mathcal{N}_\alpha\), the \(\alpha\) ordered ring times of \(\mathsf{C}_{\mathrm{w}}\) occurring during \((C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T)\) are uniformly distributed on the simplex \(\mathfrak{T}_\alpha \mathrel{\vcenter{:}}= \{(t_1, \dots, t_\alpha) \colon C_{\mathrm{burn}}< t_1 < \dots < t_\alpha < C_{\mathrm{burn}}+ T\}\) which has volume \(\mathrm{Vol}\left(\mathfrak{T}_\alpha\right) = {T^\alpha} / {\alpha!}\). We therefore have that \[\begin{align} &\;\mathbb{P}\left[\widehat\Xi \left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \nonumber \\ \geq&\;\mathbb{P}\left[\mathcal{N}_0, \mathcal{N}_\alpha \mid (\eta_0, X_0) = (\eta, x_0)\right] \frac{\alpha!}{T^{\alpha}} \!\! \int\limits_{\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha} \!\!\! \mathbb{P} \left[\Xi(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}) \mid \overrightarrow{\tau_\alpha} = \overrightarrow{t_\alpha}, \mathcal{N}_0, \mathcal{N}_\alpha, (\eta_0, X_0) = (\eta, x_0)\right] \mathrm{d} \overrightarrow{t_\alpha}. \end{align}\]

For fixed \(\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha\), the event \(\Xi(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha})\) is independent of the walker clock, and therefore we have that \(\mathbb{P} \left[\Xi(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}) \mid \overrightarrow{\tau_\alpha} = \overrightarrow{t_\alpha}, \mathcal{N}_0, \mathcal{N}_\alpha, (\eta_0, X_0) = (\eta, x_0)\right] = \mathbb{P} [\Xi(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}) \mid (\eta_0, X_0) = (\eta, x_0)]\). Furthermore, since \(C_{\mathrm{burn}}\) is constant, there exists some constant \(C_1 \in (0, 1)\) such that \(\mathbb{P}[\mathcal{N}_0] \geq C_1\) and hence, by independence of \(\mathcal{N}_0\) and \(\mathcal{N}_\alpha\), we have that \(\mathbb{P}\left[\mathcal{N}_0, \mathcal{N}_\alpha \mid (\eta_0, X_0) = (\eta, x_0)\right] \geq C_1 \mathbb{P}\left[\mathcal{N}_\alpha\right]\).

Combining everything together, it follows that \[\mathbb{P}\left[\widehat\Xi \left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \geq C_1 \mathbb{P}\left[\mathcal{N}_\alpha\right] \frac{\alpha!}{T^{\alpha}} \!\!\! \int\limits_{\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha} \!\!\! \mathbb{P} [\Xi(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}) \mid (\eta_0, X_0) = (\eta, x_0)] \mathrm{d} \overrightarrow{t_\alpha}. \label{eq:wtp2}\tag{5}\]

It will be convenient to define \(t_{\alpha + 1} \mathrel{\vcenter{:}}= C_{\mathrm{burn}}+ T\), and, given \(\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha\), to define, for all \(0 \leq i \leq \alpha\), \(T_i \mathrel{\vcenter{:}}= t_{i + 1} - t_i\) and \(\Delta_i \mathrel{\vcenter{:}}= T_i \left(\frac{\varepsilon \log n}{\mu}\right)\). By Lemma [lem:simplex95integral], there exists \(c > 0\) such that for all \(c' > c\), all \(n\) sufficiently large, with \(\delta \mathrel{\vcenter{:}}= \frac{c'}{\log n}\), \[\int_{\substack{T_0, \dots, T_\alpha \geq\delta \\ \sum_{i = 0}^\alpha T_i = T}} \;\prod_{i=0}^\alpha \left(1 - 4(K+1) n^{-(\varepsilon / 2) T_i}\right) \;\mathrm{d} \overrightarrow{T_\alpha} \geq \frac{1}{4} \frac{T^{\alpha}}{\alpha!} \left(1 - \frac{(\alpha + 1) \delta}{T}\right)^\alpha. \label{eq:wtp10}\tag{6}\]

In particular, we will choose \(c'\) sufficiently large such that \(\delta (\varepsilon \log n) > 2 \log (8(K + 1))\). Let \(\widetilde{\mathfrak{T}}_\alpha\) be the region of the simplex \(\mathfrak{T}_\alpha\) such that \((t_1, \dots, t_\alpha) \in \mathfrak{T}_\alpha\) is in \(\widetilde{\mathfrak{T}}_\alpha\) if, and only if, \(\min\limits_{0 \leq i \leq \alpha} T_i \geq \delta\).

Next fix a realisation \(\overrightarrow{u_\alpha}\) and \(\overrightarrow{t_\alpha} \in \widetilde{\mathfrak{T}}_\alpha\). For this choice of \(\overrightarrow{t_\alpha}\) it follows that, for all \(0 \leq i < \alpha\), since \(T_i (\varepsilon \log n) > 2 \log (8(K + 1))\), then \(T_i (\varepsilon \log n) > 2 \log 2\). By Lemma [lem:lem4a] we have that, \[\begin{align} &\;\mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha} ; \overrightarrow{u_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \nonumber \\ \geq& \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^\alpha} \prod_{i = 0}^{\alpha - 1} \left(1 - \tfrac{1}{(\log n)^2} - \frac{2(K+1)}{n^{(\varepsilon / 2) T_i}}\right) \! - \sum_{j \in \mathcal{L}} \mathbb{P}\left[\neg S_{[t_{j + 1} - \Delta_j, t_{j + 1}]} (R, K) \mid (\eta_0, X_0) = (\eta, x_0)\right]. \label{eq:wtp6} \end{align}\tag{7}\]

From (4 ) we have, for all \(j \in \mathcal{L}\), \(\mathbb{P}\left[\neg S_{[t_{j + 1} - \Delta_j, t_{j + 1}]} (R, K) \mid (\eta_0, X_0) = (\eta, x_0)\right] = O\left(\frac{1}{n} \left(\frac{p_{\min}}{4 d}\right)^{\alpha_{\max}}\right)\). Furthermore, \(|\mathcal{L}| \leq \alpha = O(\log n)\). Hence, in conjunction with (7 ), \[\begin{align} & \;\mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha} ; \overrightarrow{u_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \nonumber \\ \geq& \;\frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^\alpha} \prod_{i = 0}^{\alpha - 1} \left(1 - \tfrac{1}{(\log n)^2} - \frac{2(K+1)}{n^{(\varepsilon / 2) T_i}}\right) - \left(\frac{p_{\min}}{4d}\right)^{\alpha_{\max}} O\left(\tfrac{\log n}{n}\right). \label{eq:wtp7} \end{align}\tag{8}\]

For all \(0 \leq i < \alpha\), since \(T_i (\varepsilon \log n) > 2 \log (8(K + 1))\) then \[2(K + 1)n^{- (\varepsilon / 2) T_i} = 2 (K + 1) e^{- T_i (\varepsilon / 2) \log n} \leq 1/4\] and hence for all \(n\) sufficiently large we have that \(1 - (\log n)^{-2} - 2(K + 1)e^{-\frac{\mu T_i}{2}} \geq 3/4 - (\log n)^{-2} \geq 1/4\). Furthermore, since \(d \geq 3\) and \(p_{\min}< \frac{1}{d-1}\), it follows that \(1 - p_{\min}> p_{\min}\). Therefore, for all \(n\) sufficiently large, we have that \(p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell\prod_{i = 0}^{\alpha - 1} \left(1 - \frac{1}{(\log n)^2} - 2(K+1)e^{-\frac{\mu T_i}{2}}\right) \geq \left(p_{\min}/ 4\right)^{\alpha_{\max}}\). Hence from (8 ), for all \(n\) sufficiently large, \[\begin{align} \mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha} ; \overrightarrow{u_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \geq& (1 - O(\tfrac{\log n}{n})) \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^\alpha} \prod_{i = 0}^{\alpha - 1} \left(1 - \tfrac{1}{(\log n)^2} - \frac{2(K+1)}{n^{(\varepsilon / 2) T_i}}\right) \nonumber \\ >& \;\frac{1}{2} \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^\alpha} \prod_{i = 0}^{\alpha - 1} \left(1 - \tfrac{1}{(\log n)^2} - \frac{2(K+1)}{n^{(\varepsilon / 2) T_i}}\right). \label{eq:wtp8} \end{align}\tag{9}\]

By the arbitrariness of the realisation \(\overrightarrow{u_\alpha}\) and the disjointness of trajectory realisation events from Remark 1, from (9 ) we obtain that for all \(n\) sufficiently large \[\begin{align} \mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \nonumber \geq& \! \sum_{\overrightarrow{u_\alpha} \in \mathcal{R}} \frac{1}{2} \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^\alpha} \prod_{i = 0}^{\alpha - 1} \left(1 - \tfrac{1}{(\log n)^2} - \frac{2(K+1)}{n^{(\varepsilon / 2) T_i}}\right) \nonumber \\ \geq& \;\frac{1}{4} \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^{\alpha - \ell}} \prod_{i = 0}^{\alpha - 1} \left(1 - \frac{4(K+1)}{n^{(\varepsilon / 2) T_i}}\right)\label{eq:wtp9} \end{align}\tag{10}\] where the last inequality follows from the facts that \(|\mathcal{R}| = d^\ell\), and that for all \(x > 0\) and all \(n\) sufficiently large the inequality \(1 - \frac{1}{(\log n)^2} - 2(K+1)n^{-x} \geq \left(1 - \frac{1}{(\log n)^2}\right) \left(1 - 4(K+1)n^{-x} \right)\) holds and since \(\alpha = O(\log n)\), then for all \(n\) sufficiently large we have that \(\left(1 - \frac{1}{(\log n)^2}\right)^\alpha > \frac{1}{2}\).

In conjunction with (6 ) and Remark 2, from (10 ) we have that \[\begin{align} \int\limits_{\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha} \mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \mathrm{d} \overrightarrow{t_\alpha} \geq&\;\frac{1}{4} \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^{\alpha - \ell}} \!\! \int\limits_{\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha} \!\! \prod_{i = 0}^{\alpha - 1} \left(1 - \frac{4(K+1)}{n^{(\varepsilon / 2) T_i}}\right) \mathrm{d} \overrightarrow{t_\alpha} \nonumber \\ \geq& \;\frac{1}{16} \frac{T^\alpha}{\alpha!} \left(1 - \frac{(\alpha + 1) \delta}{T}\right)^\alpha \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^{\alpha - \ell}}. \label{eq:wtp11} \end{align}\tag{11}\]

Since \(\alpha \leq (4/p_{\min}) \log_{d-1} n, T \geq (1/(50 \;p_{\min}) \log_{d - 1} n)\) and \(\delta = c' / \log n = (c' \log_{d-1} e) / \log_{d-1} n\), \(\left(1 - \frac{(\alpha + 1) \delta}{T}\right)^\alpha \geq \left(1 - \left(\frac{c' \log_{d-1} e}{(1/(50 \;p_{\min}))}\right) \left(\frac{1 + (4/p_{\min}) \log_{d-1} n}{(\log_{d-1} n)^2}\right)\right)^{\alpha_{\max}} \geq \left(1 - \frac{400 c' \log_{d-1} e}{\log_{d-1} n}\right)^{(4/p_{\min}) \log_{d-1} n}\) for \(n\) sufficiently large. Hence \(\left(1 - \frac{(\alpha + 1) \delta}{T}\right)^\alpha\) is lower bounded by some constant \(C_2 \in (0, 1)\) for \(n\) sufficiently large. Therefore from (11 ) it follows that for all \(n\) sufficiently large, \[\begin{align} \frac{\alpha!}{T^{\alpha}} \int\limits_{\overrightarrow{t_\alpha} \in \mathfrak{T}_\alpha} \mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \mathrm{d} \overrightarrow{t_\alpha} \geq (C_2 / 16) \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^{\alpha - \ell}}. \label{eq:wtp12} \end{align}\tag{12}\]

The result follows by substituting (12 ) in (5 ). ◻

Proof. We will introduce some compact notation. For all \(i \in \mathcal{L}\), let \(\xi_i \mathrel{\vcenter{:}}= \xi_{x_i \not\to u_{i+1}} \left(t_{i + 1} - \Delta_i, t_{i+1}\right)\) and \(\gamma_i \mathrel{\vcenter{:}}= \frac{1-p_{\min}}{d} \left(1 - (\log n)^{-2} - 2(K + 1)n^{-(\varepsilon / 2) T_i}\right)\). For all \(i \notin \mathcal{L}\), let \(\xi_i \mathrel{\vcenter{:}}= \xi_{x_i \to x_{i+1}} \left(t_{i + 1} - \Delta_i, t_{i+1}\right)\) and \(\gamma_i \mathrel{\vcenter{:}}= \frac{p_{\min}}{d} \left(1 - n^{-\varepsilon T_i}\right)\). For all \(0 \leq i < \alpha\), let \(\xi_{[i]} = \bigcap_{j = 0}^i \xi_j\). Observe that \(\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha} ; \overrightarrow{u_\alpha}\right) = \xi_{[\alpha - 1]}\).

By the properties of the graph \(G\) and walk \(\overrightarrow{x_\alpha}\), the radius-\(R\) ball around every vertex in the walk has at most one cycle and does not lie on a cycle of length less than \(r\). Furthermore, for all \(0 \leq i \leq \alpha - 1\), since \(T_i (\varepsilon \log n) > 2 \log 2\) then \(\mu \Delta_i > 2 \log 2\). Therefore, by Lemma [lem:transition95lw95bdd] we have that if \(i \notin \mathcal{L}\) then \[\begin{align} \mathbb{P} \left[\xi_{[i]} \mid (\eta_0, X_0) = (\eta, x_0)\right] &= \mathbb{P} \left[\xi_i \mid \xi_{[i-1]}, (\eta_0, X_0) = (\eta, x_0)\right] \mathbb{P} \left[\xi_{[i-1]} \mid (\eta_0, X_0) = (\eta, x_0)\right] \\ &\geq\;\gamma_i \;\mathbb{P} \left[\xi_{[i-1]} \mid (\eta_0, X_0) = (\eta, x_0)\right]. \end{align}\]

Otherwise by Lemma [lem:stationary95lw95bdd], if \(i \in \mathcal{L}\) we have that \[\begin{align} &\;\mathbb{P} \left[\xi_{[i]} \mid (\eta_0, X_0) = (\eta, x_0)\right] \\ =&\;\mathbb{P} \left[\xi_i \mid \xi_{[i-1]}, (\eta_0, X_0) = (\eta, x_0)\right] \mathbb{P} \left[\xi_{[i-1]} \mid (\eta_0, X_0) = (\eta, x_0)\right] \\ \geq&\;\gamma_i \;\mathbb{P} \left[S_{[t_{i + 1} - \Delta_i, t_{i+1}]} (R, K), \xi_{[i-1]} \mid (\eta_0, X_0) = (\eta, x_0)\right] \\ \geq&\;\gamma_i \bigl(\mathbb{P} \left[\xi_{[i-1]} \mid (\eta_0, X_0) = (\eta, x_0)\right]\! - \mathbb{P}\left[\neg S_{[t_{i + 1} - \Delta_i, t_{i+1}]} (R, K) \mid (\eta_0, X_0) = (\eta, x_0)\right]\bigr). \end{align}\]

Therefore we inductively have that \[\mathbb{P} \left[\xi_{[\alpha - 1]} \mid (\eta_0, X_0) = (\eta, x_0)\right] \geq \prod_{i = 0}^{\alpha - 1} \gamma_i - \sum_{j \in \mathcal{L}} \left(\prod_{i = j}^{\alpha - 1} \gamma_i \right) \mathbb{P}\left[\neg S_{[t_{j + 1} - \Delta_j, t_{j + 1}]} (R, K) \mid (\eta_0, X_0) = (\eta, x_0)\right].\]

Since \(\gamma_i \in [0, 1]\) for all \(0 \leq i \leq \alpha - 1\), we obtain that \[\label{eq:l4a1} \mathbb{P} \left[\xi_{[\alpha - 1]} \mid (\eta_0, X_0) = (\eta, x_0)\right] \geq \prod_{i = 0}^{\alpha - 1} \gamma_i - \sum_{j \in \mathcal{L}} \mathbb{P}\left[\neg S_{[t_{j + 1} - \Delta_j, t_{j + 1}]} (R, K) \mid (\eta_0, X_0) = (\eta, x_0)\right].\tag{13}\]

Now, for all \(n\) sufficiently large, since for all \(0 \leq i \leq \alpha - 1\) we have that \(T_i \varepsilon \log n > 2 \log 2\), then \(1 - n^{-\varepsilon T_i} \geq 1 - n^{-(\varepsilon / 2) T_i} \geq 1 - (\log n)^{-2} - 2(K+1) n^{-(\varepsilon / 2) T_i}\). Then for all \(i \notin \mathcal{L}\) it follows that \(\gamma_i = \frac{p_{\min}}{d} \left(1 - n^{-\varepsilon T_i}\right) \geq \frac{p_{\min}}{d} \left(1 - (\log n)^{-2} - 2(K+1)n^{-(\varepsilon / 2) T_i}\right)\). By this lower bound on \(\gamma_i\) when \(i \notin \mathcal{L}\) and the definition of \(\gamma_i\) when \(i \in \mathcal{L}\), from (13 ) it follows that \[\begin{align} &\;\mathbb{P} \left[\Xi\left(\overrightarrow{x_\alpha}, \overrightarrow{t_\alpha} ; \overrightarrow{u_\alpha}\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \\ \geq& \frac{p_{\min}^{\alpha - \ell} (1 - p_{\min})^\ell}{d^\alpha} \prod_{i = 0}^{\alpha - 1} \left(1 - \tfrac{1}{(\log n)^2} - \frac{2(K+1)}{n^{(\varepsilon / 2) T_i}}\right) \! - \sum_{j \in \mathcal{L}} \mathbb{P}\left[\neg S_{[t_{j + 1} - \Delta_j, t_{j + 1}]} (R, K) \mid (\eta_0, X_0) = (\eta, x_0)\right] \end{align}\] as required. ◻

Proof. By Lemma [lem:te95prob95lw95bdd], there exists \(C_0 \in (0, 1)\) such that for \(n \in \mathbb{N}\) sufficiently large, with probability \(1 - o_n(1)\) over \(G = (V, E) \sim \mathcal{G}(d, n)\), for every \(\mu \geq \varepsilon \log n\), \(T > 0\) such that \(({1}/{(50 \;p_{\min})}) \log_{d - 1} n \leq T \leq ({4}/{p_{\min}}) \log_{d - 1} n\) and \(\alpha \in \mathbb{N}\) such that \(\alpha \leq ({4}/{p_{\min}}) \log_{d - 1} n\), and for all \(r\)-acyclic walks \(\overrightarrow{x_\alpha} \in V^{\alpha + 1}\) and \(\eta \in \{0, 1\}^E\), \[\label{eq:dcw0} \mathbb{P} \left[\widehat\Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right) \mid (\eta_0, X_0) = (\eta, x_0)\right] \geq C_0 \mathbb{P}\left[N_\mathrm{w}(C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) = \alpha\right] \frac{p_{\min}^{\alpha - \ell}(1 - p_{\min})^{\ell}}{d^{\alpha - \ell}}.\tag{14}\]

Fix such a graph \(G\) and \(\mu \geq\varepsilon \log n\). Let \(S \subseteq V\) and \(u \in V\) such that there exists \(\alpha_{\min}, \alpha_{\max}\in \mathbb{N}\) and \(\zeta \in (0, 1)\) satisfying conditions (i) and (ii) in the theorem. For convenience, for all \(x > 0\) define the functions

i. \(h_{\min}(x) \mathrel{\vcenter{:}}= \left(\frac{d-2}{d}\right) p_{\min}x\) and \(h_{\max}(x) \mathrel{\vcenter{:}}= \left(\frac{d-2}{d}\right) p_{\min}\left(x + \sqrt{x}\right)\);

ii. \(i_{\min}(x) \mathrel{\vcenter{:}}= \frac{p_{\min}}{d} x\) and \(i_{\max}(x) \mathrel{\vcenter{:}}= \frac{p_{\min}}{d} \left(x + \sqrt{x}\right)\).

Fix \(T \mathrel{\vcenter{:}}= \frac{\alpha_{\min}+ \alpha_{\max}}{2}\), and for all \(\alpha \in \mathbb{N}\) such that \(\alpha \in [\alpha_{\min}, \alpha_{\max}]\), let \[\mathcal{I}\left( \alpha \right) \mathrel{\vcenter{:}}= \left\{(h, i, \alpha - h - 2i) \in \mathbb{N}^3 \colon h_{\min}(\alpha) \leq h \leq h_{\max}(\alpha), i_{\min}(\alpha) \leq i \leq i_{\max}(\alpha)\right\}.\]

Furthermore, for all \((h, i, \ell) \in \mathcal{I}\left( \alpha \right)\), let \(\mathcal{W}_{h, i, \ell}\) be the collection of walks of length \(\alpha = h + 2i + \ell\) from \(u\) to \(S\) which are \(r\)-acyclic, have exactly \(h + 2i\) transitions corresponding to an \((h, i)\)-constrained walk, and exactly \(\ell\) stationary transitions. Noting that there are \(\binom{h + 2i + \ell}{h + 2i}\) ways of inserting \(\ell\) stationary transitions along an \((h, i)\)-constrained walk, by (ii) it follows that \(\left|\mathcal{W}_{h, i, \ell}\right | \geq \zeta \binom{h + 2i + \ell}{h+2i} \widetilde{\omega}_{h, i}\).

In particular then, by (14 ), we have that for all \(\alpha \in \mathbb{N}\) such that \(\alpha_{\min}\leq \alpha \leq \alpha_{\max}\), for all \((h, i, \ell) \in \mathcal{I}\left( \alpha \right)\), for all \(\overrightarrow{x_\alpha} \in \mathcal{W}_{h, i, \ell}\) and for all \(\eta \in \{0, 1\}^E\): \[\label{eq:dcw1} \mathbb{P} \left[\widehat\Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right) \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \geq C_0 \mathbb{P} \left[N_\mathrm{w} \left(C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T\right) = \alpha\right] \left(\frac{p_{\min}}{d}\right)^{h + 2i} (1 - p_{\min})^\ell.\tag{15}\]

Next fix \(\eta \in \{0, 1\}^E\), \(\alpha \in \mathbb{N}\) and a walk \(\overrightarrow{x_\alpha}\) starting at \(u\) and ending at some vertex in \(S\). Recall that, by our discussion in Section 5, that if \(\widehat \Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T\right)\) holds then the walker follows the trajectory \(\overrightarrow{x_\alpha}\) during the time interval \((C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T)\) and is at the end-vertex of the walk, i.e. in \(S\), at time \(C_{\mathrm{burn}}+ T\). We therefore have that, \[\mathbb{P} \left[X_{C_{\mathrm{burn}}+ T} \in S \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \geq \mathbb{P} \biggl[ \;\bigcup_{\alpha = \alpha_{\min}}^{\alpha_{\max}} \bigcup_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \bigcup_{\overrightarrow{x_\alpha} \in \mathcal{W}_{h, i, \ell}} \!\!\!\! \widehat\Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T \right)\bigg| \left(\eta_0, X_0\right) = (\eta, u) \biggr]. \label{eq:dcw3}\tag{16}\]

Next note that for any \(\alpha, \alpha' \in \mathbb{N}\) such that \(\alpha \neq \alpha'\), the events \(N_\mathrm{w}(C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) = \alpha\) and \(N_\mathrm{w}(C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) = \alpha'\) are disjoint. Also, for any \((h, i, \ell), (h', i', l') \in \mathcal{I}\left( \alpha \right)\) such that \((h, i, \ell) \neq (h', i', l')\), given any \(\overrightarrow{x_\alpha} \in \mathcal{W}_{h, i, \ell}\) and \(\overrightarrow{y_\alpha} \in \mathcal{W}_{h', i', l'}\), the events \(\widehat\Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right)\) and \(\widehat\Xi\left(\overrightarrow{y_\alpha}, C_{\mathrm{burn}}, T\right)\) are disjoint. This follows from the fact that either \(h \neq h'\) and hence the number of non-stationary transitions is distinct, or else, if \(h' = h\) then \(l \neq l'\) and therefore the number of stationary transitions is distinct.

Lastly, we have that for any \(\overrightarrow{x_\alpha}, \overrightarrow{y_\alpha} \in \mathcal{W}_{h, i, \ell}\) such that \(\overrightarrow{x_\alpha} \neq \overrightarrow{y_\alpha}\), the events \(\widehat\Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right)\) and \(\widehat\Xi\left(\overrightarrow{y_\alpha}, C_{\mathrm{burn}}, T\right)\) are disjoint. This follows from the fact that either the non-stationary transitions of both walks differ in their indices, or else they match and hence the walks must differ in at least one vertex.

Therefore from (16 ) we have that, \[\mathbb{P} \left[X_{C_{\mathrm{burn}}+ T} \in S \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \geq \sum_{\alpha = \alpha_{\min}}^{\alpha_{\max}} \sum_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \sum_{\overrightarrow{x_\alpha} \in \mathcal{W}_{h, i, \ell}} \mathbb{P} \left[ \widehat\Xi\left(\overrightarrow{x_\alpha}, C_{\mathrm{burn}}, T\right) \mid \left(\eta_0, X_0\right) = (\eta, u) \right]. \label{eq:dcw5}\tag{17}\]

Together with (15 ) and the fact that for all \((h, i, \ell) \in \mathcal{I}\left( \alpha \right)\) we have that \(|\mathcal{W}_{h, i, \ell}| > \zeta \binom{h + 2i + \ell}{h + 2i} \widetilde{\omega}_{h, i}\), \[\begin{align} &\;\mathbb{P} \left[X_{C_{\mathrm{burn}}+ T} \in S \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \nonumber \\ \geq& \;C_0 \;\zeta \sum_{\alpha = \alpha_{\min}}^{\alpha_{\max}} \mathbb{P} \left[N_\mathrm{w} (C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) = \alpha\right] \sum_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \binom{h + 2i + \ell}{h+2i}\widetilde{\omega}_{h, i} \left(\frac{p_{\min}}{d}\right)^{h+2i} (1 - p_{\min})^\ell. \label{eq:dcw6} \end{align}\tag{18}\]

Let \(a \mathrel{\vcenter{:}}= \left(1-\frac{1}{d}\right) p_{\min}\) and \(b \mathrel{\vcenter{:}}= \frac{p_{\min}}{d}\). By the lower bound on \(\widetilde{\omega}_{h,i}\) in Lemma 8, our choice \(a\) and \(b\), Stirling’s approximation for the factorial, along with the definition of \(f_\alpha\) in Lemma [lem:f95alpha95properties], we have that for all \(n\) sufficiently large: \[\begin{align} &\sum_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \binom{h + 2i + \ell}{h+2i}\widetilde{\omega}_{h, i} \left(\frac{p_{\min}}{d}\right)^{h+2i} (1 - p_{\min})^\ell \\ \geq& \sum\limits_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \frac{h+1}{h+i+1} \frac{(h + 2i + \ell)!}{(h+i)! \;i! \;\ell!} \left(\frac{(d-1)p_{\min}}{d}\right)^{h+i} \left(\frac{p_{\min}}{d}\right)^{i} (1-p_{\min})^\ell \\ \geq& \;\frac{1}{2 \pi} \;\alpha^{\alpha} \! \sum\limits_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \frac{h+1}{h+i+1} \sqrt{\frac{\alpha}{(h+i) \;i \;\ell}} \left(\frac{a}{h+i}\right)^{h+i} \left(\frac{b}{i}\right)^{i} \left(\frac{1-a-b}{\alpha - h - 2i}\right)^{\alpha - h - 2i} \\ \geq& \;C_1 \;\alpha^{\alpha - 1} \! \sum\limits_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \exp\Big(f_\alpha (h+i, i)\Big) \end{align}\] where \(C_1 \mathrel{\vcenter{:}}= \frac{1}{3200 \pi}\), since \(\sqrt{\frac{\alpha}{(h+i) \;i \;\ell}} \geq \frac{1}{\alpha}\) and \(\frac{h+1}{h+i+1} \geq \frac{h_{\min}\left(({1}/{(50 \;p_{\min})}) \log n\right)+1}{h_{\max}\left(({4}/{p_{\min}}) \log_{d-1} n\right) + i_{\max}\left(({4}/{p_{\min}}) \log_{d-1} n\right) + 1} \geq 2 \pi C_1\).

Letting \(C_2 \mathrel{\vcenter{:}}= \left(\frac{d-2}{2}\right)\left(\frac{p_{\min}}{d}\right)^2\), for all \(n\) sufficiently large we have \(|\mathcal{I}\left( \alpha \right)| \geq C_2 \alpha\). Also, letting \(C_3 \mathrel{\vcenter{:}}= \exp\left(-\frac{a+b}{2(1-a-b)}\right)\), by Lemma [lem:f95alpha95properties] we have that for all \((h, i, \ell) \in \mathcal{I}\left( \alpha \right)\): \(\exp\left(f_\alpha (h + i, i)\right) \geq C_3 \exp\left(f_\alpha (a \alpha, b \alpha)\right) \geq C_3 \alpha^{-\alpha}\). Therefore, \[\sum\limits_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \exp\left(f_\alpha (h + i, i)\right) \geq C_2 C_3 \alpha \exp\left(f_\alpha (a \alpha, b \alpha)\right) \geq \frac{C_2 C_3}{\alpha^{\alpha-1}}.\]

Combining everything together, we obtain that: \[\label{eq:dcw7} \sum_{(h, i, \ell) \in \mathcal{I}\left( \alpha \right)} \binom{h + 2i + \ell}{h+2i}\widetilde{\omega}_{h, i} \left(\frac{p_{\min}}{d}\right)^{h+2i} (1 - p_{\min})^\ell \geq C_1 C_2 C_3.\tag{19}\]

From (18 ) and (19 ), defining \(C \mathrel{\vcenter{:}}= \frac{C_0 C_1 C_2 C_3}{2}\), we have that \[\begin{align} \mathbb{P} \left[X_{C_{\mathrm{burn}}+ T} \in S \mid \left(\eta_0, X_0\right) = (\eta, u)\right] &\geq 2 C \zeta \sum_{\alpha = \alpha_{\min}}^{\alpha_{\max}} \mathbb{P} \left[N_\mathrm{w} (C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) \alpha\right] \\ &= 2 C \zeta \cdot \mathbb{P} \left[N_\mathrm{w} (C_{\mathrm{burn}}, C_{\mathrm{burn}}+ T) \in \left[\alpha_{\min}, \alpha_{\max}\right]\right] \\ &\geq C \zeta \end{align}\] where the last inequality follows from Lemma [lem:poisson95concentration]. The result follows. ◻

Proof. By Lemma [lem:phase195walk95counts], with probability \(1 - o_n(1)\) over \(G \sim \mathcal{G}(d, n)\), for any vertex \(u\) and \(h, i \in \mathbb{N}\) such that \({R}/{10} \leq h \leq {R}/{5}\) and \(i \leq {R}/{5}\), there are at least \(d - 2\) neighbours of \(u\) from which there are \(\frac{\widetilde{\omega}_{h, i}}{2}\) walks which are \((h, i)\)-constrained, \(r\)-acyclic and end at a vertex in \(V_{\mathrm{good}}\).

Fix such a graph \(G\), vertex \(u \in V\), and define \(\alpha_{\min}\mathrel{\vcenter{:}}= \left\lceil\frac{1}{50} \left({d}/{d - 2}\right) \left({1}/{p_{\min}}\right) \log_{d - 1} n\right\rceil\) and \(\alpha_{\max}\mathrel{\vcenter{:}}= \left\lfloor\frac{3}{100} \left({d}/{d - 2}\right) \left({1}/{p_{\min}}\right) \log_{d - 1} n \right\rfloor\). Observe that this choice of \(\alpha_{\min}\) and \(\alpha_{\max}\) satisfies condition (i) of Lemma 1. Furthermore, for all \(\alpha, h, i \in \mathbb{N}\) such that \(\alpha \in [\alpha_{\min}, \alpha_{\max}]\), \(i \in \left[\frac{p_{\min}}{d} \alpha, \frac{p_{\min}}{d} \left(\alpha + \sqrt{\alpha}\right)\right]\) and \(h \in \left[\left(\frac{d-2}{d}\right) p_{\min}\alpha, \left(\frac{d-2}{d}\right) p_{\min}\left(\alpha + \sqrt{\alpha}\right)\right]\), it follows that \(h\) and \(i\) satisfy \({R}/{10} \leq h \leq {R}/{5}\) and \(i \leq {R}/{5}\).

Therefore there are \(d - 2\) neighbours of \(u\), say \(u_1, \dots, u_{d-2}\), such that for all \(1 \leq j \leq d - 2\), there are \(\frac{\widetilde{\omega}_{h, i}}{2}\) walks from \(u_j\) to a vertex in \(V_{\mathrm{good}}\) which are \(r\)-acyclic and \((h, i)\)-constrained, and hence condition (ii) of Lemma 1 is satisfied for every \(u_j\) with \(S = V_{\mathrm{good}}\) and \(\zeta = 1/2\).

Hence by Lemma 1, with probability \(1 - o_n(1)\) over the choice of \(G\), noting that we invoke it at time \(t = 1\) and that \(T_1 = 1 + C_{\mathrm{burn}}+ \frac{\alpha_{\max}+ \alpha_{\min}}{2}\), there exists a constant \(C \in (0, 1)\) such that for all \(1 \leq j \leq d - 2\) we have that \[\label{eq:pob2} \mathbb{P} \left[X_{T_1} \in V_{\mathrm{good}}\mid X_1 = u_j \right] \geq {C}/{2}.\tag{20}\]

It remains to show that, with probability \(\Omega(1)\), the walker transitions during \((0, 1)\) from \(u\) to one of the neighbours \(u_1, \dots, u_{d - 2}\) and then stays there until time \(t = 1\). Recall the definition of the transition event \(\xi_{u \to u'} (t, t')\) as in Definition 7 and let \(\sigma_1\) denote the first ring time of the walker clock. If \(N_{\mathrm{w}}(0, 1) = 1\) and \(\xi_{u \to u_j} (0, \sigma_1)\) both hold for some \(1 \leq j \leq d - 2\), the walker clock rings exactly once in \((0, 1)\), the edge \(\{u, u_j\}\) refreshes open during \((0, \sigma_1)\), and at time \(\sigma_1\) the walker examines that edge. Hence the walker transitions from \(u\) to \(u_j\); since there are no further rings in \((\sigma_1, 1)\), it remains there until time \(t = 1\).

Conditioned on \(N_{\mathrm{w}}(0, 1) = 1\), the time \(\sigma_1\) is uniformly distributed on \((0, 1)\). Therefore, for all \(1 \leq j \leq d - 2\) and for all \(\eta \in \{0, 1\}^E\), \[\label{eq:pob3} \mathbb{P} \left[X_1 = u_j \mid \left(\eta_0, X_0\right) = (\eta, u) \right] \geq \int_0^1 \mathbb{P}\left[\xi_{u \to u_j} (0, x) \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \mathbb{P}\left[N_{\mathrm{w}}(0, 1) = 1\right] \mathrm{d} x.\tag{21}\]

By Lemma [lem:transition95lw95bdd] and the fact that \(\mathbb{P}\left[N_{\mathrm{w}}(0, 1) = 1\right] = {1}/{e}\), \[\label{eq:pob4} \left(\int_0^1 \mathbb{P}\left[\xi_{u \to u_j} (0, x) \mid \left(\eta_0, X_0\right) = (\eta, u)\right] \mathrm{d} x\right) \mathbb{P}\left[N_{\mathrm{w}}(0, 1) = 1\right] = \frac{p_{\min}}{e d} \left(1 - \frac{1 - e^{-\mu}}{\mu}\right).\tag{22}\]

Since \(\mu = \Omega(\log n)\), \(\left(1 - \frac{1 - e^{-\mu}}{\mu}\right) \geq {1}/{2}\) for \(n\) sufficiently large. Moreover, for each fixed \(x > 0\), the events \(\xi_{u \to u_1}(0, x), \dots, \xi_{u \to u_{d - 2}}(0, x)\) are pairwise disjoint. Therefore for all \(n\) sufficiently large, by (21 ) and (22 ), we have that \(\mathbb{P} \left[X_1 \in \{u_1, \dots, u_{d - 2}\} \mid \left(\eta_0, X_0\right) = (\eta, u) \right] \geq \left(\frac{d - 2}{d}\right) \frac{p_{\min}}{2 e}\). The result follows. ◻

Proof. By Lemma [lem:sparse95good95set95size], with probability \(1 - o_n(1)\) over \(G \sim \mathcal{G}(d, n)\), for any \(v \in V_{\mathrm{good}}\) there exists \(S_v \subseteq V\) such that \(\left|S_v\right| = n - o(n)\) and for all \(h, i \in \mathbb{N}\) such that \(H_{\min}(d, n)\leq h \leq H_{\max}(d, n)\) and \(i \leq \left({4}/{p_{\min}}\right) \log_{d - 1} n\), the following holds: For every \(x \in S_v\) there are at least \(\frac{1}{4n} \widetilde{\omega}_{h, i}\) walks from \(v\) to \(x\) which are \((h, i)\)-constrained and \(r\)-acyclic.

Fix such a graph \(G\), vertex \(v \in V_{\mathrm{good}}\), and let \(\alpha_{\min}\mathrel{\vcenter{:}}= \left\lceil\frac{d}{d-2} \frac{1}{p_{\min}} \left(\log_{d-1} n + 2\log_{d-1}\log n \right)\right\rceil\) and \(\alpha_{\max}\mathrel{\vcenter{:}}= \left\lfloor\frac{d}{d-2} \frac{1}{p_{\min}}(1+\frac{1}{40})\log_{d-1} n\right\rfloor\). Observe that this choice of \(\alpha_{\min}\) and \(\alpha_{\max}\) satisfies condition (i) of Lemma 1. Furthermore, for all \(\alpha, i, h \in \mathbb{N}\) such that \(\alpha \in [\alpha_{\min}, \alpha_{\max}]\), \(i \in \left[\frac{p_{\min}}{d} \alpha, \frac{p_{\min}}{d} \left(\alpha + \sqrt{\alpha}\right)\right]\) and \(h \in \left[\left(\frac{d-2}{d}\right) p_{\min}\alpha, \left(\frac{d-2}{d}\right) p_{\min}\left(\alpha + \sqrt{\alpha}\right)\right]\), it follows that \(h\) and \(i\) satisfy \(H_{\min}(d, n)\leq h \leq H_{\max}(d, n)\) and \(i \leq \left({4}/{p_{\min}}\right) \log_{d - 1} n\).

Therefore there exists \(S_v \subseteq V\) such that \(|S_v| = n - o(n)\) and for all \(x \in S_v\), there are \(\frac{1}{4n}\widetilde{\omega}_{h, i}\) walks from \(v\) to \(x\) which are \(r\)-acyclic and \((h, i)\)-constrained, and hence condition (ii) of Lemma 1 is satisfied with \(S = \{x\}\) and \(\zeta = {1}/{4n}\).

Hence by Lemma 1, with probability \(1 - o_n(1)\) over the choice of \(G\), noting that we invoke it at time \(t = T_1\) and that \(T_2 - T_1 = C_{\mathrm{burn}}+ \frac{\alpha_{\max}+ \alpha_{\min}}{2}\), there exists \(C \in (0, 1)\) such that for all \(x \in S_v\) and \(\hat{\eta} \in \{0, 1\}^E\), we have that \(\mathbb{P}\left[X_{T_2} = x \mid \left(\eta_{T_1}, X_{T_1}\right) = \left(\hat{\eta}, v\right)\right] \geq {C}/{4 n}\). The result follows. ◻

Proof. Here we briefly remark why we can state the results of [1] in this slightly different form. For a boundary condition \(\eta\) on \(\partial B_R(v)\), by \(\mathcal{J}_{B_R (v), \eta}\) we will denote the set of vertices in \(B_R (v)\) which belong to non-singleton components of the partition \(\eta\left[\partial B_R (v)\right]\).

First, their proof relies on the discrete-time joint-revealing procedure on the ball \(B_R(v)\) and its boundary. In particular, their procedure does not reveal any information on the random variables associated with the edges inside \(B_R (v)\) up to time \(t\).

Instead, they consider the interior with all edges wired open, hence maximising connectivity through the ball, and only consider the random variables associated with the exterior edges for the dynamics. This gives a configuration \(\tilde{\eta}_{\langle t \rangle}\) which dominates the true configuration \(\eta_{\langle t \rangle}\), and hence sparsity on \(\tilde{\eta}_{\langle t \rangle}\) via the exterior implies sparsity on \(\eta_{\langle t \rangle}\) via the exterior.

Furthermore, in their proof they show that, jointly over the configuration model and \(\tilde{\eta}_{\langle t \rangle}\), for any \(k > 1\), the probability of \(\left\{\big|\mathcal{J}_{B_R (v), \eta_{\langle t \rangle}}\big| < k\right\}\) is dominated by the probability of the event \(S_{\langle t \rangle} \left(B_R (v), k\right)\), which in turn is bounded above by \(n^{-\delta k \wedge 4}\).

The constant \(4\) that appears in the exponent can be carefully controlled. We desire it to be \(c_1 + c_2 + 2\); let \(M \geq \left\lceil\frac{c_1 + c_2 + 2}{\delta}\right\rceil\). We can then set \(\Lambda\) sufficiently large in the proof of their Proposition 2 (dependent on \(M\), among other parameters), such that the contribution from the term \(\mathbb{P}\left[\sum_{k \leq k_\emptyset} |\mathcal{V}_k| \geq \Lambda \left|\mathcal{V}_0\right|\right]\) is bounded above by \(O(n^{-M})\) by their Lemma 6. The proof of Proposition 2 then proceeds as usual, with the final Markov inequality over the configuration model applied with \(n^{-(c_2 + 1)}\) instead of \(n^{-2}\).

This then gives that, with probability \(1 - O\left(n^{-(c_1 + 1)}\right)\) over \(G\) sampled from the configuration model, \(\sup\limits_{v \in V} \mathbb{P} \left[\neg S_{\langle t \rangle}(B_R(v), K) \mid \eta_{\langle 0 \rangle} = \eta'\right] \leq n^{-(c_2 + 1)}\). From this, one can deduce the analogue of their Theorem 5 by union bounding over the vertices and conditioning on simple graphs in the configuration model. ◻

Proof. Recall that we will use \(S_t (R, K)\) and \(S_{\langle t \rangle} (R, K)\) to differentiate between the continuous and discrete-time analogues, respectively, of the external sparsity event in Definition 9.

Let \(\rho \mathrel{\vcenter{:}}= \left(\frac{4}{p_{\min}}\right) \frac{\log \left({4d}/{p_{\min}}\right)}{\log (d - 1)}\). By Theorem [thm:k95sparse95burn95in], there exist constants \(D_\mathrm{burn}, K > 0\) such that for all \(T \in \mathbb{N}\) satisfying \(T \geq D_\mathrm{burn} n \log n\): With probability \(1 - O\left(n^{-3}\right)\) over \(G \sim \mathcal{G}(d, n)\), \[\label{eq:ssp1} \mathbb{P} \left[\neg S_{\langle T \rangle} (R, K) \mid \eta_{\langle 0 \rangle} = \eta\right] = O\left(n^{-(\rho + 3)}\right), \qquad \forall \eta \in \{0, 1\}^E.\tag{23}\]

Let \(C > 0\) be a constant. Let the edge clocks refresh at rate \(\mu \geq\varepsilon \log n\). Let \(t' > t \geq C\) such that \(t' - t \leq (4/p_{\min}) \log_{d-1} n\). Define \(\Delta \mathrel{\vcenter{:}}= (t' - t) \left(\frac{\varepsilon \log n}{\mu}\right)\) and \(t_0 \mathrel{\vcenter{:}}= t' - \Delta - C \left(\frac{\varepsilon \log n}{\mu}\right)\); observe that \(t' - \Delta = t_0 + C \left(\frac{\varepsilon \log n}{\mu}\right)\) and that for all \(\mu \geq \varepsilon \log n\) we have that \(t_0 = t' - (t' - t + C) \left(\frac{\varepsilon \log n}{\mu}\right) \geq t' - (t' - t + C) \geq t - C \geq 0\) since \(t \geq C\).

By the Markov property, we have that, for all \(\eta \in \{0, 1\}^E\), \[\mathbb{P} [\neg S_{[t' - \Delta, t']} (R, K) \mid \eta_0 = \eta] = \sum_{\eta' \in \{0, 1\}^E} \mathbb{P} [\neg S_{[t' - \Delta, t']} (R, K) \mid \eta_{t_0} = \eta'] \mathbb{P}\left[\eta_{t_0} = \eta' \mid \eta_0 = \eta\right]\] and therefore it suffices to show that, for all \(\eta' \in \{0, 1\}^E\), \(\mathbb{P} \left[\neg S_{[t' - \Delta, t']} \left(R, K\right) \mid \eta_{t_0} = \eta'\right] = O\left(n^{-(\rho + 1)}\right)\).

During the interval \(\left[t_0, t' - \Delta\right)\), which has length \(C \left(\frac{\varepsilon \log n}{\mu}\right)\), the number of edge refreshes is \(N_1 (C) \sim \mathsf{Poisson}\left(\left({C d \varepsilon}/{2}\right) n \log n\right)\). Let \(T_\mathrm{burn} \mathrel{\vcenter{:}}= \left\lceil D_\mathrm{burn} n \log n\right\rceil\). Since \(\mathbb{E}\left[N_1 (C)\right] = \left({C d \varepsilon}/{2}\right) n \log n\), then by concentration there exists \(C_{\mathrm{burn}}> 0\) such that \(\mathbb{P}\left[N_1 (C_{\mathrm{burn}}) < T_\mathrm{burn} \right] \leq O\left(n^{-(\rho + 1)}\right)\). Also, there exists \(C_1 > 0\) such that \(\mathbb{P}\left[N_1(C_{\mathrm{burn}}) > C_1 n \log n\right] \leq O\left(n^{-(\rho + 1)}\right)\). Define \(T_{1, \mathrm{max}} \mathrel{\vcenter{:}}= \left\lfloor C_1 n \log n \right\rfloor\).

During the interval \(\left[t' - \Delta, t'\right]\), the number of edge refreshes is \(N_2 \sim \mathsf{Poisson}\left((d \varepsilon / 2) (t' - t) n \log n)\right)\). Since \(t' - t \leq (4 / p_{\min}) \log_{d-1} n\), we have that \(\mathbb{E}\left[N_2\right] \leq \left(\frac{2 d \varepsilon}{p_{\min}\log(d - 1)}\right) n (\log n)^2\), and by concentration there exists \(C_2 > 0\) such that \(\mathbb{P}\left[N_2 > C_2 n (\log n)^2 \right] \leq O\left(n^{-(\rho + 1)}\right)\). Let \(T_{2, \mathrm{max}} \mathrel{\vcenter{:}}= \left\lfloor C_2 n (\log n)^2\right\rfloor\).

Note that, since Poisson clocks are independent over disjoint time intervals, \(N_1 (C_{\mathrm{burn}})\) and \(N_2\) are independent. Given \(T_1, T_2 \in \mathbb{N}\) and \(\eta' \in \{0, 1\}^E\), conditioned on \(N_1 (C_{\mathrm{burn}}) = T_1\) and \(N_2 = T_2\), the continuous-time dynamics on \([t_0, t']\), started at \(\eta_{t_0} = \eta'\), is distributed as the discrete-time chain run for \(T_1 + T_2\) steps from the initial state \(\eta_{\langle 0 \rangle} = \eta'\), where at each step an edge is chosen independently and uniformly at random. Define \(T_\mathrm{max} \mathrel{\vcenter{:}}= T_{1, \mathrm{max}} + T_{2, \mathrm{max}}\). By a simple union bound, for all \(\eta' \in \{0, 1\}^E\), \[\begin{align} & \;\mathbb{P} \left[\neg S_{[t' - \Delta, t']} \left(R, K\right) \mid \eta_{t_0} = \eta'\right] \nonumber \\ =& \sum_{T_1 = 0}^\infty \sum_{T_2 = 0}^\infty \mathbb{P} \left[\neg S_{\langle[T_1, T_1 + T_2]\rangle} \left(R, K\right) \mid \eta_{\langle 0 \rangle} = \eta'\right] \mathbb{P}\left[N_1 (C_{\mathrm{burn}}) = T_1\right] \mathbb{P}\left[N_2 = T_2\right] \nonumber \\ \leq& \sum_{T_1 = 0}^\infty \sum_{T_2 = 0}^\infty \sum_{T = T_1}^{T_1 + T_2} \mathbb{P} \left[\neg S_{\langle T \rangle} \left(R, K\right) \mid \eta_{\langle 0 \rangle} = \eta'\right] \mathbb{P}\left[N_1 (C_{\mathrm{burn}}) = T_1\right] \mathbb{P}\left[N_2 = T_2\right] \nonumber \\ \leq& \;\mathbb{P}\left[N_1 (C_{\mathrm{burn}}) < T_\mathrm{burn}\right] + \mathbb{P}\left[N_1 (C_{\mathrm{burn}}) > T_{1, \mathrm{max}}\right] + \mathbb{P}\left[N_2 > T_{2, \mathrm{max}}\right] \nonumber \\ & \;+ \sum_{T_1 = T_\mathrm{burn}}^{T_{1, \mathrm{max}}} \sum_{T_2 = 0}^{T_{2, \mathrm{max}}} \sum_{T = T_1}^{T_1 + T_2} \mathbb{P} \left[\neg S_{\langle T \rangle} \left(R, K\right) \mid \eta_{\langle 0 \rangle} = \eta'\right] \mathbb{P}\left[N_1 (C_{\mathrm{burn}}) = T_1\right] \mathbb{P}\left[N_2 = T_2\right] \nonumber \\ \leq & \;\mathbb{P}\left[N_1 (C_{\mathrm{burn}}) \notin \left[T_\mathrm{burn}, T_{1, \mathrm{max}}\right]\right] + \mathbb{P}\left[N_2 > T_{2, \mathrm{max}}\right] + \sum_{T = T_\mathrm{burn}}^{T_\mathrm{max}} \mathbb{P} \left[\neg S_{\langle T \rangle} \left(R, K\right) \mid \eta_{\langle 0 \rangle} = \eta'\right]. \label{eq:ssp2} \end{align}\tag{24}\]

For all \(T \in \mathbb{N}\) such that \(T_\mathrm{burn} \leq T \leq T_\mathrm{max}\), let \(\mathcal{G}_{\langle T \rangle}\) be the family of graphs satisfying (23 ). Since \(T_\mathrm{max} = \Theta\left(n (\log n)^2\right)\), then by a simple union bound, with probability \(1 - O\left(n^{-1}\right)\) over \(G \sim \mathcal{G}(d, n)\), \(G\) is in \(\cap_{T = T_\mathrm{burn}}^{T_\mathrm{max}} \mathcal{G}_{\langle T \rangle}\), since for our choice of \(K\), the probability that \(G \notin \mathcal{G}_{\langle T \rangle}\) is \(O\left(n^{-3}\right)\). Now for every such graph \(G\) we have that for all \(T \in \mathbb{N}\) such that \(T_\mathrm{burn} \leq T \leq T_\mathrm{max}\) and for all \(\eta' \in \{0, 1\}^E\), \(\mathbb{P} \left[\neg S_{\langle T \rangle} (R, K) \mid \eta_{\langle 0 \rangle} = \eta'\right] = O\left(n^{-(\rho + 3)}\right)\). Furthermore, by our choices of \(C_{\mathrm{burn}}\), \(T_{1, \mathrm{max}}\) and \(T_{2, \mathrm{max}}\), we have that \(\mathbb{P}\left[N_1 (C_{\mathrm{burn}}) \notin \left[T_\mathrm{burn}, T_{1, \mathrm{max}}\right]\right] = O\left(n^{-(\rho + 1)}\right)\) and \(\mathbb{P}\left[N_2 > T_{2, \mathrm{max}}\right] = O\left(n^{-(\rho + 1)}\right)\).

Therefore, from these facts in conjunction with (24 ), \[\mathbb{P} \left[\neg S_{[t' - \Delta, t']} \left(R, K\right) \mid \eta_{t_0} = \eta'\right] = O\left(n^{-(\rho + 1)}\right) + \sum_{T = T_\mathrm{burn}}^{T_\mathrm{max}} O\left(n^{-(\rho + 3)}\right) = O\left(n^{-(\rho + 1)}\right)\] noting that \(T_\mathrm{max} = \Theta\left(n (\log n)^2\right)\). The result follows. ◻

Proof. First note that \(\mathcal{F}_{\tau \vert \mathsf{C}(0, T)} (x) = \mathbb{P}\left[\tau \leq x \mid \mathsf{C}(0, T)\right] = \frac{\mathbb{P}\left[\mathsf{C}(0, x]\right]\mathbb{P}\left[\neg\mathsf{C}(x, T)\right]}{\mathbb{P}\left[\mathsf{C}(0, T)\right]} = \frac{e^{\mu x} - 1}{e^{\mu T} - 1}\). Taking the derivative with respect to \(x\), we obtain that \(f_{\tau \vert \mathsf{C}(0, T)} (x) = \dfrac{\mu e^{\mu x}}{e^{\mu T} - 1}\). ◻

Proof. Let \(e \mathrel{\vcenter{:}}= \{u, u'\}\). If the edge \(e\) refreshes during \((t, t')\), i.e. the event \(\mathsf{C}_e(t, t')\) holds, and during the last ring \(\tau_e (t, t')\) it holds that \(U_e \left(\tau_e (t, t')\right) < p_{\min}\), then \(e\) is refreshed open independent of whether it is a cut edge or not at time \(\tau_e (t, t')\). Therefore, the events \(V_u (t') = u'\), \(\mathsf{C}_e(t, t')\) and \(U_e \left(\tau_e (t, t')\right) < p_{\min}\) imply the event \(\xi_{u \to u'} (t, t')\). Hence, \[\mathbb{P} \left[\xi_{u \to u'} \left(t,t'\right) \mid (\eta_t, X_t) = (\eta, v)\right] \geq \mathbb{P} \left[V_{u}\left(t'\right) = u', \mathsf{C}_e\left(t,t'\right), U_e \left(\tau_e(t, t')\right) < p_{\min}\mid (\eta_t, X_t) = (\eta, v)\right].\]

The events \(V_u (t') = u'\), \(\mathsf{C}_e(t, t')\) and \(U_e \left(\tau_e (t, t')\right) < p_{\min}\) concern the ringing of Poisson clocks and sampling of uniforms during the time interval \((t, t')\), which are independent of the state at time \(t\). Furthermore, the random variable \(V_u\) is independent of the environment random variables, namely \(U_e\) and \(\mathsf{C}_e\).

We therefore have that, \[\begin{align} &\;\mathbb{P} \left[V_{u}\left(t'\right) = u', \mathsf{C}_e\left(t,t'\right), U_e \left(\tau_e(t, t')\right) < p_{\min}\mid (\eta_t, X_t) = (\eta, v)\right] \\ =&\;\mathbb{P}\left[V_{u}\left(t'\right) = u'\right] \mathbb{P}\left[U_e \left(\tau_e(t, t')\right) < p_{\min}\mid \mathsf{C}_e\left(t,t'\right)\right] \mathbb{P}\left[\mathsf{C}_e\left(t,t'\right)\right]. \end{align}\]

Since \(V_{u}\left(t'\right)\) is uniform on the \(d\) neighbours of \(u\), then \(\mathbb{P}\left[V_{u}\left(t'\right) = u'\right] = 1/d\). By the probability of a Poisson clock ringing in a given time interval, we have \(\mathbb{P}\left[\mathsf{C}_e\left(t,t'\right)\right] = 1 - e^{-\mu \left(t' - t\right)}\). Lastly, since \(U_e\) is uniform on \((0, 1)\), we have \(\mathbb{P}\left[U_e \left(\tau_e(t, t')\right) < p_{\min}\mid \mathsf{C}_e\left(t,t'\right)\right] = p_{\min}\). The result follows. ◻

Proof. Since there is at most one cycle in \(B_R (u)\), then \(\left|C_e (R)\right| \leq 1\). Moreover, if such a cycle containing \(e\) exists in \(B_R (u)\), its length must be at least \(r\) (otherwise \(u\) lies on a cycle of length less than \(r\)) and hence \(\left|E_{u, r}(\mathbf{c})\right| \geq r\). By complementation and a simple union bound (noting the independence of the \(\mathcal{E}\) events for distinct edges in Remark 3), \[\mathbb{P} \left[\neg \xi_{u, e}^{\mathrm{acyclic}}\left(t, t + x\right) \right] \leq \sum_{\mathbf{c} \in C_e(R)} \prod_{\substack{e' \in E_{u, r}(\mathbf{c}) \\ e' \neq e}} \mathbb{P} \left[\neg \mathcal{E}_{e'} (t, t + x)\right] \leq \left(p + (1-p)e^{-\mu x}\right)^{r - 1}\] where the last inequality follows using \(\left|C_{e} (R)\right| \leq 1\), the fact that any such cycle must have at least \(r - 1\) edges distinct from \(e\) that are a distance at most \(r\) from \(u\), and the upper bound on \(\mathbb{P}\left[\neg \mathcal{E}_{e'}(t, t + x)\right]\) given in (25 ). The result follows. ◻

Proof. First note that, by disjointness of events over \(F \subseteq \partial B_R (u)\), we have that \[\mathbb{P}\left[\xi_{u, e}^{\mathrm{path}}\left(t, t + x\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] = \sum_{\substack{F \subseteq \partial B_R (u) \\ |F| \leq K}} \mathbb{P}\left[\mathcal{P}^{F}_{u, e} (t, t + x) \cap S^F_{t + x} \left(B_R (u)\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right].\]

Now, by Remark 3, the event \(\mathcal{P}^{F}_{u, e} (t, t + x)\) is independent of the state at time \(t\). Furthermore, recall that the external sparsity event \(S^F_{t + x} \left(B_R (u)\right)\) is independent of the edge clocks and uniforms associated with edges inside \(B_R(u)\) up to time \(t + x\). On the other hand, \(\mathcal{P}^{F}_{u, e} (t, t + x)\) is an event concerning the clocks and uniforms associated with edges inside \(B_R(u)\) during \((t, t + x)\). Hence \(S^F_{t + x} \left(B_R (u)\right)\) and \(\mathcal{P}^{F}_{u, e} (t, t + x)\) are also independent. Consequently, we have that \[\mathbb{P}\left[\xi_{u, e}^{\mathrm{path}}\left(t, t + x\right) \mid \left(\eta_t, X_t\right) = (\eta', v)\right] = \sum_{\substack{F \subseteq \partial B_R (u) \\ |F| \leq K}} \!\! \mathbb{P}\left[\mathcal{P}^{F}_{u, e} (t, t + x)\right] \mathbb{P}\left[S^F_{t + x} \left(B_R (u)\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right].\]

Since there is at most one cycle in \(B_R(u)\), then given \(F \subseteq \partial B_R (u)\) such that \(|F| \leq K\), the number of paths inside \(B_R (u)\) from \(u\) to a vertex in \(F\) is at most \(2K\) and hence \(\left|P\left(B_R(u), F\right)\right| \leq 2K\). Indeed, suppose that there is some vertex \(v\) in \(F\) such that there are three or more paths in \(B_R (u)\) from \(u\) to \(v\); then there are at least two cycles in \(B_R(u)\), which is a contradiction.

Next, by complementation and a simple union bound (noting the independence of the \(\mathcal{E}\) events for distinct edges in Remark 3), we have that \[\mathbb{P} \left[\neg \mathcal{P}^{F}_{u, e} (t, t + x) \right] \leq \sum_{\mathbf{p} \in P\left(B_R(u), F\right)} \prod_{\substack{e' \in E_{e, (r, R)}(\mathbf{p}) \\ e' \neq e}} \mathbb{P} \left[\neg \mathcal{E}_{e'} (t, t + x)\right] \text{d} x \leq 2K \left(p + (1-p)e^{-\mu x}\right)^{R - r - 1}\] where the last inequality follows from \(\left|P\left(B_R(u), F\right)\right| \leq 2K\), the fact that for any \(\mathbf{p} \in P\left(B_R(u), F\right)\) we have \(\left|E_{e, (r, R)} (\mathbf{p})\right| \geq R - r\), and the upper bound on \(\mathbb{P}\left[\neg \mathcal{E}_{e'}(t, t + x)\right]\) given in (25 ).

For \(n\) sufficiently large we have \(R - r - 1 \geq {R}/{2}\), since \(R = \Theta(\log n)\) and \(r = \Theta(\log \log n)\). Therefore, for \(n\) sufficiently large, \(\mathbb{P} \left[\neg \mathcal{P}^{F}_{u, e} (t, t + x) \right] \leq 2K \left(p + (1-p)e^{-\mu x}\right)^{{R}/{2}}\). From Definition 9, we have that \(S_{t+x} \left(B_R(u), K\right)\) is the disjoint union of the events \(S^F_{t+x} \left(B_R (u)\right)\) for all \(F \subseteq \partial B_R (u)\) such that \(|F| \leq K\). Combining everything together, we have that \[\begin{align} &\;\mathbb{P}\left[\xi_{u, e}^{\mathrm{path}}\left(t, t + x\right) \mid \left(\eta_t, X_t\right) = (\eta', v)\right] \\ \geq& \left(1 - 2K \left(p + (1-p)e^{-\mu x}\right)^{{R}/{2}}\right) \sum_{\substack{F \subseteq \partial B_R (u) \\ |F| \leq K}} \mathbb{P}\left[S^F_{t + x} \left(B_R (u)\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \\ =& \left(1 - 2K \left(p + (1-p)e^{-\mu x}\right)^{{R}/{2}}\right) \mathbb{P}\left[S_{t+x} \left(B_R (u), K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \\ \geq& \left(1 - 2K \left(p + (1-p)e^{-\mu x}\right)^{{R}/{2}}\right) \mathbb{P}\left[S_{t+x} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \end{align}\] where the last inequality follows from the fact that \(S_{t+x} \left(R, K\right) \subseteq S_{t+x} \left(B_R (u), K\right)\). The result follows. ◻

Proof. Since \(e^{-y}\) is strictly decreasing in \(y\) and for all \(y \geq 0\), \(e^{-y} \leq 1\), we have that, in particular, \(p + (1-p)e^{-\mu x} \leq 1\) for \(x \in [0, {\Delta}/{2}]\), and \(p + (1-p)e^{-\mu x} \leq p + (1-p)e^{-{\mu \Delta}/{2}}\) for \(x \in [{\Delta}/{2}, \Delta]\).

Also, since \(\mu \Delta > 2 \log 2\), then \(p + (1-p) e^{-{\mu \Delta}/{2}} < {(1+p)}/{2} \leq {(1+p_\mathrm{u}(q, d))}/{2}\), which is also strictly less than \(1\). In particular, by our choice of \(r\), namely \(r \mathrel{\vcenter{:}}= \dfrac{3 \log_{d-1} \log n}{\log_{d-1} (2 / (1 + p_\mathrm{u}(q, d)))}\), there exists some \(C > 0\) such that for all \(n\) sufficiently large, \(\left({(1+p_\mathrm{u}(q, d))}/{2}\right)^{r - 1} < C(\log n)^{-3}\).

Therefore, splitting the integral over these two regions of \(x\), we have that, for all \(n\) sufficiently large, \[\begin{align} \int_{0}^{\Delta} \frac{\mu e^{\mu x}}{e^{\mu \Delta} - 1} \left(p + (1-p)e^{-\mu x}\right)^{r - 1} \text{d} x &\leq \frac{1}{e^{{\mu \Delta}/{2}} + 1} + \int_{{\Delta}/{2}}^{\Delta} \frac{\mu e^{\mu x}}{e^{\mu \Delta} - 1} \left(\frac{1+p_\mathrm{u}(q, d)}{2}\right)^{r - 1} \text{d} x \nonumber \\ &\leq e^{-{\mu \Delta}/{2}} + C(\log n)^{-3} \end{align}\] and hence the result follows. ◻

Proof. First note that, for \(n\) sufficiently large, we have that \(R > r > 1\) and hence for all \(0 \leq x \leq \Delta\), the event \(\xi_{u, e}^{\mathrm{cut}} (t, t + x)\) is independent of the clock \(\mathsf{C}_e\) and uniform \(U_e\) associated with the edge \(e\). Indeed, \(\xi_{u, e}^{\mathrm{cut}} (t, t + x)\) is the event that \(\xi_{u, e}^{\mathrm{acyclic}}\left(t, t + x\right)\) and \(\xi_{u, e}^{\mathrm{path}}\left(t, t + x\right)\) both hold, where \(\xi_{u, e}^{\mathrm{acyclic}}\left(t, t + x\right)\) is an event about clocks and uniforms during \((t, t + x)\) for edges in \(E\left(B_r (u)\right)\) distinct from \(e\) while \(\xi_{u, e}^{\mathrm{path}}\left(t, t + x\right)\) is an event about the clocks and uniforms up to time \(t + x\) for edges in \(E\left(B_R (u)\right) \setminus E\left(B_r (u)\right)\).

Hence for all \(0 \leq x \leq \Delta\), we have that the events \(\xi_{u, e}^{\mathrm{cut}} (t, t + x)\) and \(\mathsf{C}_e(t, t + \Delta)\) are independent, the events \(\xi_{u, e}^{\mathrm{acyclic}}\left(t, t + x\right)\) and \(\xi_{u, e}^{\mathrm{path}}\left(t, t + x\right)\) are independent, and lastly the event \(\xi_{u, e}^{\mathrm{acyclic}}\left(t, t + x\right)\) is independent of the state at time \(t\). Therefore, in conjunction with Lemma 3, \[\begin{align} &\;\mathbb{P} \left[\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e(t, t + \Delta)\right) \mid \mathsf{C}_{e}\left(t, t + \Delta\right), (\eta_t, X_t) = (\eta, v)\right] \nonumber \\ =& \int_{0}^{\Delta} \!\! \frac{\mu e^{\mu x}}{e^{\mu \Delta} - 1} \;\mathbb{P}\left[\xi_{u, e}^{\mathrm{cut}} (t, t + x) \mid (\eta_t, X_t) = (\eta, v) \right] \text{d} x \nonumber \\ =& \int_{0}^{\Delta} \!\! \frac{\mu e^{\mu x}}{e^{\mu \Delta} - 1} \;\mathbb{P}\left[\xi_{u, e}^{\mathrm{acyclic}} (t, t+x) \right] \mathbb{P}\left[\xi_{u, e}^{\mathrm{path}}(t, t+x) \mid (\eta_t, X_t) = (\eta, v) \right] \text{d} x. \label{clp:eq1} \end{align}\tag{26}\]

Recall from Definition 9 that \(S_{[t, t + \Delta]} (R, K)\) is the event that \(S_{t+x} (R, K)\) holds for all \(0 \leq x \leq \Delta\). Then, \(\mathbb{P}\left[S_{t+x} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \geq \mathbb{P}\left[S_{[t, t + \Delta]} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right]\).

Together with Lemmas 4 and 5, we have that \[\begin{align} &\;\mathbb{P}\left[\xi_{u, e}^{\mathrm{acyclic}} (t, t+x) \right] \mathbb{P}\left[\xi_{u, e}^{\mathrm{path}}(t, t+x) \mid (\eta_t, X_t) = (\eta, v) \right] \nonumber \\ \geq&\;\mathbb{P}\left[S_{t+x} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \left(1 - 2K \left(p + (1-p)e^{-\mu x}\right)^{{R}/{2}}\right) \left(1 - \left(p + (1-p)e^{-\mu x}\right)^{r-1} \right). \nonumber \\ >&\;\mathbb{P}\left[S_{[t, t + \Delta]} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \left(1 - (2K + 1) \left(p + (1-p)e^{-\mu x}\right)^{r - 1}\right)\label{clp:eq2} \end{align}\tag{27}\] where the last inequality follows from the facts that \((1 - z)(1 - y) > 1 - z - y\) for \(z, y > 0\), and \(R/2 \geq r - 1\) for sufficiently large \(n\).

Hence, by (26 ) and (27 ), we obtain that \[\begin{align} &\;\mathbb{P} \left[\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e\right) \mid \mathsf{C}_{e}\left(t, t + \Delta\right), (\eta_t, X_t) = (\eta, v)\right] \\ \geq& \;\mathbb{P}\left[S_{[t, t + \Delta]} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \left(1 - (2K + 1) \int_{0}^{\Delta} \!\! \frac{\mu e^{\mu x}}{e^{\mu \Delta} - 1} \;\left(p + (1-p)e^{-\mu x}\right)^{r - 1} \;\mathrm{d} x \right). \end{align}\]

The result follows by Lemma 6. ◻

Proof. Let \(e \mathrel{\vcenter{:}}= \{u, u'\}\). If the edge \(e\) refreshes during \((t, t')\), i.e. the event \(\mathsf{C}_e(t, t')\) holds, and during the last ring \(\tau_e (t, t')\) both \(U_e (\tau_e (t, t')) > p_{\min}\) and \(\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right)\) hold, then \(e\) is a cut edge in the configuration at time \(\tau_e (t, t')\), then \(e\) is refreshed closed at time \(\tau_e (t, t')\) and remains closed until time \(t'\).

Therefore, the events \(V_u (t') = u'\), \(\mathsf{C}_e(t, t')\), \(U_e (\tau_e (t, t')) > p_{\min}\) and \(\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right)\) imply the event \(\xi_{u \not\to u'} (t, t')\). Hence, \[\begin{align} &\;\mathbb{P}\left[\xi_{u \not\to u'} (t, t') \mid (\eta_t, X_t) = (\eta, v)\right] \\ \geq&\;\mathbb{P} \left[V_u (t') = u', \mathsf{C}_e(t, t'), U_e (\tau_e (t, t')) > p_{\min}, \xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right) \mid (\eta_t, X_t) = (\eta, v)\right] \end{align}\]

The events \(V_u (t') = u'\), \(\mathsf{C}_e(t, t')\) and \(U_e \left(\tau_e (t, t')\right) > p_{\min}\) concern the ringing of Poisson clocks and sampling of uniforms during \((t, t')\), which are independent of the state at time \(t\). Furthermore, the random variable \(V_u\) is independent of all environment random variables, namely \(U_e\) and \(\mathsf{C}_e\), and in particular is independent of the event \(\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right)\) which only concerns environment random variables. Also, the event \(U_e \left(\tau_e (t, t')\right) > p_{\min}\) is independent of \(\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right)\), since \(\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right)\) by construction is an event about the ringing of clocks and sampling of uniforms associated with edges distinct from \(e\) up to the last ring time \(\tau_e (t, t')\) of \(e\) in the time interval \((t, t')\). We therefore have that, \[\begin{align} &\;\mathbb{P} \left[V_u (t') = u', \mathsf{C}_e(t, t'), U_e (\tau_e (t, t')) > p_{\min}, \xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right) \mid (\eta_t, X_t) = (\eta, v)\right] \\ =&\;\mathbb{P}\left[V_{u}\left(t'\right) = u'\right] \mathbb{P}\left[U_e \left(\tau_e (t, t')\right) > p_{\min}\mid \mathsf{C}_e\left(t,t'\right)\right]\mathbb{P}\left[\mathsf{C}_e\left(t,t'\right)\right] \\ &\;\mathbb{P}\left[\xi_{u, e}^{\mathrm{cut}} \left(t, \tau_e (t, t')\right) \mid \mathsf{C}_e\left(t, t'\right), (\eta_t, X_t) = (\eta, v)\right]. \end{align}\]

Since \(V_{u}\left(t'\right)\) is uniform on the \(d\) neighbours of \(u\), then \(\mathbb{P}\left[V_{u}\left(t'\right) = u'\right] = 1/d\). By the probability of a Poisson clock ringing in a time interval, we have \(\mathbb{P}\left[\mathsf{C}_e\left(t,t'\right)\right] = 1 - e^{-\mu \left(t' - t\right)}\). Also, since \(U_e\) is uniform on \((0, 1)\), \(\mathbb{P}\left[U_e \left(\tau_e(t, t')\right) > p_{\min}\mid \mathsf{C}_e\left(t,t'\right)\right] = 1 - p_{\min}\). Lastly, by Lemma 7, noting that all necessary conditions are met, we have that for \(n\) sufficiently large, \[\begin{align} &\;\mathbb{P}\left[\xi_{u, e}^{\mathrm{cut}} (t, \tau_e)\mid \mathsf{C}_e\left(t, t'\right), (\eta_t, X_t) = (\eta, v)\right] \\ \geq&\;\mathbb{P}\left[S_{[t, t']} \left(R, K\right) \mid \left(\eta_t, X_t\right) = \left(\eta, v\right)\right] \left(1 - \frac{1}{(\log n)^2} - (2K + 1) e^{-\mu (t' - t)/2}\right). \end{align}\]

The result follows by combining all these lower bounds together, noting that \[(1 - e^{-a})(1 - c - (2b + 1) e^{-a/2}) \geq 1 - c - 2(b + 1)e^{-a/2}\] for all \(a, b > 0\) and \(0 < c < 1\). ◻

Proof. First note that we can embed the infinite \((d-1)\)-ary tree into the infinite \(d\)-regular tree, with the roots of both trees identified. Hence every \((h, i)\)-constrained walk on \(\widetilde{\mathcal{T}}\) is uniquely mapped to an \((h, i)\)-constrained walk on \(\mathcal{T}\) under this embedding. Therefore, \(\omega_{h,i} > \widetilde{\omega}_{h,i}\).

We will next determine \(\widetilde{\omega}_{h,i}\). Starting at the root \(\widetilde{\rho}\) of \(\widetilde{\mathcal{T}}\), to reach depth \(h\) in a walk of length \(h +2i\), exactly \(h + i\) transitions must increase the depth by \(1\), and \(i\) transitions must decrease the depth by \(1\). The number of such walks is equivalent to the number of walks of length \(h + 2i\) on \(\mathbb{Z}\) starting at \(0\) and ending at \(h\) which never become negative. By Bertrand’s Ballot Theorem, the number of such walks is known to be \(\frac{h+1}{h+i+1} \binom{h + 2i}{h+i}\). For each of the \(h + i\) downward transitions we have \(d-1\) choices, since each vertex has exactly \(d-1\) children.

Therefore the total number of such walks is \(\frac{h+1}{h+i+1} \binom{h + 2i}{h+i} (d-1)^{h+i}\). The result follows. ◻

Proof. Fix a vertex \(v\) and a walk in \(\mathcal{T}_v\) of length \(h + 2i\) from the root to depth \(h\) that passes through a vertex \(\hat{\rho}\) labelled \(u\). Re-rooting the tree \(\mathcal{T}_v\) at \(\hat{\rho}\) results in another labelled tree isomorphic to \(\mathcal{T}_u\), with the image of the walk passing through the new root \(\hat{\rho}\).

In particular, the walks \(w_{h,i}(v,u)\) in \(\mathcal{T}_v\) correspond to walks in \(\mathcal{T}_u\) of length \(h + 2i\) which:

i. pass through the root \(\hat{\rho}\) of \(\mathcal{T}_u\),

ii. start at some vertex \(x \in V(\mathcal{T}_u)\) labelled \(v\),

iii. and end at a vertex distance \(h\) away from \(x\) in the tree \(\mathcal{T}_u\).

Note that a walk in \(w_{h,i}(v,u)\) on \(\mathcal{T}_v\) may correspond to multiple such walks on \(\mathcal{T}_u\), depending on how many times a vertex labelled \(u\) appears on the walk.

Therefore to upper bound \(\sum_{v \in V} |w_{h,i} (v,u)|\), it suffices to count the number of walks of length \(h+2i\) in \(\mathcal{T}_u\) which start at any vertex, pass through the root, and end at a vertex distance \(h\) away from the starting vertex. Let \(\mathcal{W}\) be the set of all such walks in \(\mathcal{T}_u\).

Given \(r \in \mathbb{N}\) and \(x \in V(\mathcal{T}_u)\), let \(\partial B(x,r)\) be the set of vertices in \(\mathcal{T}_u\) which are distance \(r\) away from \(x\). Then \(|\partial B(x, r)| = d(d-1)^{r-1}\) by regularity, and hence the cardinality is invariant of \(x\). Also, given \(t \in \mathbb{N}\) and \(x, y \in V(\mathcal{T}_u)\), let \(\mathcal{W}_{x, t} (y)\) be the set of all walks of length \(h+2i\) in \(\mathcal{T}_u\) starting at \(x\) which pass through \(y\) at step \(t\).

Now, any walk in \(\mathcal{W}\) must start at most a distance \(h+i\) away from the root \(\hat{\rho}\) of \(\mathcal{T}_u\), since they have to pass through the root and end a distance \(h\) from the start. Therefore, for every walk in \(\mathcal{W}\) there exists \(r \in \mathbb{N}\) such that \(0 \leq r \leq h + i\), the walk starts at a vertex \(x \in \partial B(\hat{\rho}, r)\), and the walk passes through the root \(\hat{\rho}\) at step \(t \in \mathbb{N}\) where \(r \leq t \leq h + 2i\). In particular we have that \[\label{eq:pcl1} \mathcal{W}= \bigcup_{r = 0}^{h+i} \bigcup_{t = r}^{h+2i} \bigcup_{x \in \partial B(\hat{\rho}, r)} \mathcal{W}_{x,t}(\hat{\rho}).\tag{28}\]

Let \(\mathcal{W}_{x,t}^r\) be the union of \(\mathcal{W}_{x,t} (y)\) for all \(y \in \partial B(x,r)\). Note that for any two distinct vertices \(y, z \in V(\mathcal{T}_u)\), the sets \(\mathcal{W}_{x,t} (y)\) and \(\mathcal{W}_{x,t} (z)\) are disjoint, since the walks differ at step \(t\). Therefore, \[\label{eq:pcl2} \left|\mathcal{W}_{x,t}^r\right| = \sum_{y \in \partial B(x,r)} \left|\mathcal{W}_{x,t} (y)\right|.\tag{29}\]

By symmetry in \(\mathcal{T}_u\), for any two vertices \(y, z \in \partial B(x,r)\), the number of walks of length \(h+2i\) which start at \(x\) and end at distance \(h\) from \(x\) while passing through \(y\) and \(z\) respectively at step \(t\) is equal, which is to say that \(|\mathcal{W}_{x,t} (y)| = |\mathcal{W}_{x,t} (z)|\). Therefore in conjunction with (29 ) and the fact that \(|\partial B(x, r)| = d(d-1)^{r-1}\), for all \(y \in \partial B(x,r)\) we have that \[\label{eq:pcl3} |\mathcal{W}_{x,t}^r| = d(d-1)^{r-1} |\mathcal{W}_{x,t} (y)|.\tag{30}\]

Furthermore, \(\mathcal{W}_{x,t}^r\) is a subset of all walks of length \(h+2i\) in \(\mathcal{T}_u\) starting at \(x\) which end a distance \(h\) away from \(x\), and hence by Remark 6 we have that \[\label{eq:pcl4} |\mathcal{W}_{x,t}^r| \leq \omega_{h,i}.\tag{31}\]

In particular, if the root \(\hat{\rho}\) is in \(\partial B (x,r)\) then by (30 ) and (31 ) we have that \[\label{eq:pcl5} |\mathcal{W}_{x,t} (\hat{\rho})| \leq \frac{\omega_{h,i}}{d(d-1)^{r-1}}.\tag{32}\]

Hence from (28 ) and (32 ) along with the fact that \(|\partial B(\hat{\rho}, r)| = d(d-1)^{r-1}\), we have that \[\begin{align} |\mathcal{W}| \leq \sum_{r = 0}^{h+i} \sum_{t = r}^{h+2i} \sum_{x \in \partial B(\hat{\rho}, r)} |\mathcal{W}_{x,t} (\hat{\rho})| \leq \sum_{r = 0}^{h+i} \sum_{t = r}^{h+2i} \sum_{x \in \partial B(\hat{\rho}, r)} \frac{\omega_{h,i}}{d(d-1)^{r-1}} = \frac{1}{2}(h+i+1)(h+3i+2) \;\omega_{h,i} \end{align}\] as required. ◻

Proof. Since \(r = O(\log \log n)\) then \(\sqrt{r} (d-1)^{3r/2 - 1} = o(n)\) and by Corollary 1, the number of vertices on cycles of length at most \(r\) is, with probability \(1 - o(1)\) over \(G \sim \mathcal{G}(d, n)\), at most \((\log n)(d-1)^r\). Let \(\mathcal{B}\) be the set of vertices contained in such cycles.

Fix \(h, i \in \mathbb{N}\) such that \(h, i \leq \left({4}/{p_{\min}}\right) \log_{d - 1} n\). Given a vertex \(u \in \mathcal{B}\), for every vertex \(v \in V\) let \(w_{h,i}(v, u)\) be the set of \((h, i)\)-constrained walks from \(v\) which pass through \(u\).

For a vertex \(v\) to be \((h, i)\)-sparse, it suffices that \(\sum_{u \in \mathcal{B}} |w_{h,i}(v,u)| < ({1}/{(\log n)^3}) \omega_{h,i}\), which is to say that the \((h, i)\)-constrained walks from \(v\) which pass through a vertex in \(\mathcal{B}\) only make up at most a \({1}/{(\log n)^3}\) fraction of all possible \((h, i)\)-constrained walks from \(v\).

Define \(V_\textrm{bad} (h, i) \mathrel{\vcenter{:}}= \{v \in V \colon \sum_{u \in \mathcal{B}} |w_{h,i}(v,u)| \geq ({1}/{(\log n)^3}) \omega_{h,i}\}\). By the previous remark, every vertex in \(V \setminus V_\textrm{bad} (h, i)\) is \((h, i)\)-sparse. Hence it suffices to upper bound the size of \(V_\textrm{bad} (h, i)\). By Lemma 9 we have that \[\sum_{u \in \mathcal{B}} \sum_{v \in V} |w_{h,i}(v,u)| \leq |\mathcal{B}| (1/2)(h+i+1)(h+3i+2) \;\omega_{h,i} \leq \left(1 + {8}/{p_{\min}}\right)^2 |\mathcal{B}| (\log_{d - 1} n)^2 \omega_{h,i}\] where the last inequality follows from \(h, i \leq ({4}/{p_{\min}}) \log_{d - 1} n\). We also have the following lower bound, \[\sum_{u \in \mathcal{B}} \sum_{v \in V} |w_{h,i}(v,u)| \geq \sum_{v \in V_\mathrm{bad} (h, i)} \sum_{u \in \mathcal{B}} |w_{h,i}(v,u)| \geq |V_\textrm{bad} (h, i)| ({1}/{(\log n)^3}) \omega_{h,i}\] where the last inequality follows by the definition of \(V_\textrm{bad} (h, i)\).

Therefore \(|V_\textrm{bad} (h, i)| ({1}/{(\log n)^3}) \omega_{h,i} \leq \left(1 + {8}/{p_{\min}}\right)^2 |\mathcal{B}| (\log_{d - 1} n)^2 \omega_{h,i}\) and hence \[|V_\textrm{bad} (h, i)| \leq \left(\frac{1 + {8}/{p_{\min}}}{\log(d - 1)}\right)^2 (d - 1)^r (\log n)^6\] since \(\left|\mathcal{B}\right| \leq (\log n) (d-1)^r\). Let \(V_{\mathrm{bad}} = \bigcup\limits_{h, i \leq ({4}/{p_{\min}}) \log_{d-1} n} V_{\mathrm{bad}} (h, i)\). Then by the upper bound on each \(V_{\mathrm{bad}} (h, i)\), we have that \(\left|V_{\mathrm{bad}}\right| = O\left((d - 1)^r (\log n)^8\right)\). In particular, all the vertices in \(V \setminus V_{\mathrm{bad}}\) are \((h, i)\)-sparse for all \(h, i \leq ({4}/{p_{\min}}) \log_{d - 1} n\) and hence the result follows. ◻

Proof. By Lemma [lem:rrg95glbl95geom], with probability \(1 - o(1)\) over \(G \sim \mathcal{G}(d, n)\), there exist \(n - O\left(\mathrm{polylog}(n)\right)\) vertices which are \((h, i)\)-sparse for all \(h, i \in \mathbb{N}\) such that \(h, i \leq \left({4}/{p_{\min}}\right) \log_{d - 1} n\).

Furthermore, by Lemma 2.1 in [7], we have that, with probability \(1 - o_n(1)\) over \(G \sim \mathcal{G}(d, n)\), every ball of radius \(R\) in \(G\) contains at most one cycle. Hence, with probability \(1 - o_n(1)\) over \(G \sim \mathcal{G}(d, n)\), both of these properties hold. Fix such a graph \(G\).

Let \(S\) be the set of all vertices in \(G\) which are \((h, i)\)-sparse for all \(h, i \in \mathbb{N}\) such that \(h, i \leq \left({4}/{p_{\min}}\right) \log_{d - 1} n\).

Fix a vertex \(u \in V\) and consider the subgraph \(B\) induced by the ball \(B_R (u)\). Since there is at most one cycle in this subgraph, deleting \(u\) from \(B\) results in at least \(d - 1\) components; in particular there must be \(d - 2\) rooted trees \(T_1, \dots, T_{d-2}\), whose roots are neighbours of \(u\), call them \(u_1, \dots, u_{d-2}\) respectively. Furthermore, the (at most) unique cycle in \(B\) is entirely contained in \(H \mathrel{\vcenter{:}}= B \setminus \cup_{j = 1}^{d-1} T_j\).

Fix \(1 \leq j \leq d-2\) and \(h, i \in \mathbb{N}\) such that \({R}/{10} \leq h \leq {R}/{5}\) and \(i \leq {R}/{5}\). The sub-tree \(T_j\) corresponding to \(u_j\) has degree \(d - 1\) at the root and degree \(d\) at all other non-leaf vertices. Hence \(T_j\) is a \((d-1)\)-ary tree of depth \(R - 1\). Since \(h + i \leq {2R}/{5} \leq R - 1\) and \((h, i)\)-constrained walks never exceed depth \(h + i\), the number of \((h, i)\)-constrained walks on \(T_j\) is equal to that on the infinite \((d-1)\)-ary tree, namely \(\widetilde{\omega}_{h, i}\).

Consider an \((h, i)\)-constrained walk on \(T_j\). Suppose a vertex in this walk is contained in a cycle of length less than \(r\) in \(G\). Since the walk reaches a depth of at most \(h + i \leq {2R}/{5}\) and the cycle has length at most \(r\) (which is less than \({R}/{10}\) for all \(n\) sufficiently large), then every vertex in the cycle is at distance at most \({R}/{2}\) away from \(u_j\) in \(G\).

Therefore, since \(u_j\) is a neighbour of \(u\), every vertex in the cycle is at distance at most \(({R}/{2}) + 1\) away from \(u\) in \(G\). Therefore the cycle is entirely contained in the subgraph \(B\) induced by the ball \(B_R (u)\). However, this cycle contains at least one vertex in \(T_j\), and the (at most) unique cycle in \(B\) must be entirely contained in \(H\), which is disjoint from \(T_j\). Therefore such a cycle cannot exist, and hence every such walk in \(T_j\) does not visit a vertex on a cycle of length less than \(r\).

Now for every vertex in \(T_j\) at depth greater than \(k = \log_{d-1} \log n\) but no more than \(R - k - 1\), the ball radius \(k\) around such a vertex is does not contain any cycle in \(G\), and hence every such vertex is a \(k\)-root. This is illustrated in Figure 1. Given \(n\) sufficiently large, it follows that for all \(h \in \mathbb{N}\) such that \({R}/{10} \leq h \leq {R}/{5}\), all the vertices in \(T_j\) at depth \(h\) are \(k\)-roots.

Furthermore, since \({R}/{10} \leq h\) and \(R = (1/5) \log_{d-1} n\), we have that \((d-1)^h = \Omega\left(n^{1/50}\right)\). Since \(|V \setminus S| = O\left(\mathrm{polylog}(n)\right)\), it follows that for \(n\) sufficiently large, \(|V \setminus S| < \frac{1}{2} (d-1)^h\). Therefore, at least half of the vertices at depth \(h\) in \(T_j\) are \(k\)-roots and in \(S\), i.e., in \(V_{\mathrm{good}}\).

Hence for all \(h, i \in \mathbb{N}\) satisfying \({R}/{10} \leq h \leq {R}/{5}\) and \(i \leq {R}/{5}\), at least half of the \((h, i)\)-constrained walks from \(u_j\) in \(T_j\) end at a vertex in \(V_{\mathrm{good}}\), and we have shown that such a walk on \(T_j\) never visits a cycle of length less than \(r\). Since there are at least \(d - 2\) such neighbours of \(u\), the result follows. ◻

Proof. By Lemmas 10 and 10, with probability \(1 - o(1)\) over \(G \sim \mathcal{G}(d, n)\), for a given \(k\)-root \(u\) there exists a set \(S'_u\) of \(k\)-roots with size \(n - o(n)\), such that for all \(h \in \mathbb{N}\) satisfying \(H_{\min}(d, n)\leq h \leq H_{\max}(d, n)\) and for all \(v \in S'_u\): \(\left|\mathcal{P}_{h} (u, v)\right| \geq \left(1-o(1)\right) \left({1}/{n}\right) d(d-1)^{h - 1}\). In particular, for all \(n\) sufficiently large, we have that \(\left|\mathcal{P}_{h} (u, v)\right| \geq ({1}/{2n}) d(d-1)^{h - 1}\).

Fix such a graph \(G\), \(u \in V_{\mathrm{good}}\) and \(v \in S'_u\). For all \(i \in \mathbb{N}\), by Remark 9 we have that the paths in \(\mathcal{P}_h(u,v)\) correspond to \(({1}/{2n}) \omega_{h, i}\) walks from \(u\) which are \((h, i)\)-constrained and end at \(v\).

Let \(\mathcal{W}_{h, i} (u, v)\) correspond to this collection of walks. By the previous remarks, \(\left|\mathcal{W}_{h, i} (u, v)\right| > ({1}/{2n}) \omega_{h, i}\). Clearly for any two distinct vertices \(v, w \in S'_u\), these collections are disjoint (namely since they end at distinct vertices). Let \(\mathcal{W}_{h, i} (u)\) be the collection of all \((h, i)\)-constrained walks from \(u\), where \(\left|\mathcal{W}_{h, i} (u)\right| = \omega_{h, i}\).

Next fix \(h, i \in \mathbb{N}\) such that \(H_{\min}(d, n)\leq h \leq H_{\max}(d, n)\) and \(i \leq \left({4}/{p_{\min}}\right) \log_{d - 1} n\). Since \(u \in V_{\mathrm{good}}\) then it is \((h, i)\)-sparse and hence at most \(\left({1}/{(\log n)^3}\right) \omega_{h, i}\) of the walks in \(\mathcal{W}_{h, i} (u)\) are not \(r\)-acyclic. Let this collection of “bad" walks be \(\mathcal{W}^\mathrm{bad}_{h, i} (u)\), and for all \(v \in S'_u\) let \(\mathcal{W}^\mathrm{bad}_{h, i} (u, v) \mathrel{\vcenter{:}}= \mathcal{W}^\mathrm{bad}_{h, i} (u) \cap \mathcal{W}_{h, i} (u, v)\). Note that all of these sets are pairwise disjoint and that their union is a subset of \(\mathcal{W}^\mathrm{bad}_{h, i} (u)\).

Let \(S^\mathrm{bad}_u (h, i)\) be the subset of \(S'_u\) such that \(v \in S^\mathrm{bad}_u (h, i)\) if, and only if, \(\left|\mathcal{W}^\mathrm{bad}_{h, i} (u, v)\right| > \frac{1}{2} \left|\mathcal{W}_{h, i} (u, v)\right|\). Then, \[\begin{align} \left|S^\mathrm{bad}_u (h, i)\right| \frac{\omega_{h, i}}{4n} \leq \sum_{v \in S^\mathrm{bad}_u (h, i)} \frac{\left|\mathcal{W}_{h, i} (u, v)\right|}{2} < \sum_{v \in S^\mathrm{bad}_u (h, i)} \left|\mathcal{W}^\mathrm{bad}_{h, i} (u, v)\right| \leq \left|\mathcal{W}^\mathrm{bad}_{h, i} (u)\right| < \frac{\omega_{h, i}}{(\log n)^3} \end{align}\] and hence \(\left|S^\mathrm{bad}_u (h, i)\right| = O\left({n}/{(\log n)^3}\right)\).

Define \(S_u \mathrel{\vcenter{:}}= S'_u \setminus \bigcup\limits_{h, i} S^\mathrm{bad}_u (h, i)\). Since \(\left|S^\mathrm{bad}_u (h, i)\right| = O\left({n}/{(\log n)^3}\right)\) for all \(H_{\min}(d, n)\leq h \leq h_{\max}\) and \(i \leq ({4}/{p_{\min}}) \log_{d - 1} n\), then \(|S_u| \geq |S'_u| - O\left({n}/{(\log n)}\right)\). Since \(|S'_u| = n - o(n)\) it follows that \(|S_u| = n - o(n)\).

We have therefore constructed a set \(S_u\) of size \(n - o(n)\), such that for all \(H_{\min}(d, n)\leq h \leq h_{\max}\) and \(i \leq ({4}/{p_{\min}}) \log_{d - 1} n\) and for all \(v \in S_u\), there are at least \(({1}/{4 n}) \omega_{h, i}\) walks from \(u\) to \(v\) which are \((h, i)\)-constrained and \(r\)-acyclic. The result follows. ◻

Proof. Fix \(c > 0\) and \(c' > c\). We will eventually choose an appropriate value of \(c\). Let \(\delta \mathrel{\vcenter{:}}= {c'}/{(\log n)}\). Let \(x_0, \dots, x_\alpha \in [0, 1]\) be the shifted and rescaled variables satisfying \(x_i = \frac{T_i - \delta}{T - (\alpha + 1)\delta}\) for all \(0 \leq i \leq \alpha\), and \(\sum_{i=0}^\alpha x_i = 1\). The Jacobian for this change of variables satisfies \(\mathrm{d} \overrightarrow{T_\alpha} = \left(T - (\alpha + 1)\delta\right)^\alpha \;\mathrm{d} \overrightarrow{x}\), and the simplex is bijectively mapped onto the unit simplex \[\mathcal{K}_{\alpha} \mathrel{\vcenter{:}}= \left\{x_0, \dots, x_\alpha \in [0, 1] \colon x_0 + \dots + x_\alpha = 1 \right\}\] with volume \(\mathrm{Vol}(\mathcal{K}_\alpha) = \frac{1}{\alpha!}\). Let \(\mu_0 \mathrel{\vcenter{:}}= \varepsilon \log n\) and \(\lambda \mathrel{\vcenter{:}}= \frac{1}{2} \mu_0 \left(T - (\alpha + 1) \delta\right)\). Then, for all \(0 \leq i \leq \alpha\), we have that \(1 - C n^{-(\varepsilon / 2) T_i} = 1 - C \exp\left(-(\mu_0 / 2) T_i\right) = 1 - C \exp\left(-(\mu_0 / 2) \delta - \lambda x_i\right)\), and therefore \[\label{eq:sil1} \int_{\substack{T_0, \dots, T_\alpha \geq \delta \\ \sum_{i = 0}^\alpha T_i = T}} \;\prod_{i=0}^\alpha \left(1 - C n^{-(\varepsilon / 2) T_i}\right) \;\mathrm{d} \overrightarrow{T_\alpha} = \left(T - (\alpha + 1)\delta\right)^\alpha \int_{\mathcal{K}_{\alpha}} \prod_{i = 0}^\alpha \left(1 - C e^{-(\mu_0 / 2) \delta - \lambda x_i}\right) \;\mathrm{d} \overrightarrow{x}.\tag{33}\]

Let \(\gamma(c) \mathrel{\vcenter{:}}= C e^{-c \left({\varepsilon}/{2}\right)}\). Since \(\mu_0 = \varepsilon \log n\) and \(\delta = \frac{c'}{\log n} > \frac{c}{\log n}\), then, for all \(0 \leq i \leq \alpha\), we have that \(1 - C e^{-(\mu_0 / 2) \delta - \lambda x_i} \geq 1 - \gamma(c) e^{-\lambda x_i}\). By inclusion-exclusion, we also have that \[\label{eq:sil2} \prod_{i = 0}^\alpha \left(1 - \gamma(c) e^{-\lambda x_i}\right) = \sum_{j = 0}^{\alpha+1} (-1)^j \left(\gamma(c)\right)^j \sum_{\substack{S \subseteq \{0, 1, \dots, \alpha\} \\ |S| = j}} e^{-\lambda \sum_{i\in S} x_i}\tag{34}\]

By symmetry over the simplex, we have that each subset of size \(j\) contributes equally to the summation above, and therefore we can rewrite (34 ) as \[\label{eq:sil3} \prod_{i = 0}^\alpha \left(1 - \gamma(c) e^{-\lambda x_i}\right) = \sum_{j = 0}^{\alpha+1} (-1)^j \left(\gamma(c)\right)^j \binom{\alpha + 1}{j} e^{-\lambda \sum_{i = 1}^j x_{i-1}}.\tag{35}\]

Letting \(M_j (\lambda) \mathrel{\vcenter{:}}= \left(\gamma(c)\right)^j \binom{\alpha + 1}{j} \int_{\mathcal{K}_{\alpha}} e^{-\lambda \sum_{i = 1}^j x_{i-1}} \;\mathrm{d} \overrightarrow{x}\) for \(0 \leq j \leq \alpha + 1\), we therefore have that \[\label{eq:sil4} \int_{\mathcal{K}_{\alpha}} \prod_{i = 0}^\alpha \left(1 - C e^{-(\mu_0 / 2) \delta - \lambda x_i}\right) \;\mathrm{d} \overrightarrow{x} \geq \sum_{j = 0}^{\alpha+1} (-1)^j M_j(\lambda).\tag{36}\]

We will proceed to show that for \(j \geq 1\), the differences \(M_j (\lambda) - M_{j+1} (\lambda)\) are non-negative. For \(1 \leq j \leq \alpha\), let \(X_j = x_0 + \dots + x_{j-1}\). Under the uniform distribution on \(\mathcal{K}_{\alpha}\), \((x_0, \dots, x_\alpha)\) follow a \(\mathrm{Dirichlet}(1, \dots, 1)\) distribution, and by the aggregation property for the Dirichlet distribution, \((X_j, 1 - X_j)\) follows a \(\mathrm{Dirichlet}(j, \alpha - j + 1)\) distribution. From the marginal properties of Dirichlet distributions, we therefore have that \(X_j\) follows a \(\mathrm{Beta}(j, \alpha - j + 1)\) distribution with probability density function \[\begin{align} f_{X_j}(x) = \frac{\alpha!}{(j-1)! \;(\alpha - j)!} x^{j - 1}(1 - x)^{\alpha - j}, & \forall x \in [0, 1]. \end{align}\]

We therefore have that \[M_j (\lambda) = \mathrm{Vol}(\mathcal{K}_{\alpha}) \cdot \left(\gamma(c)\right)^j \binom{\alpha + 1}{j} \cdot \frac{\alpha!}{(j-1)! \;(\alpha - j)!} \int_0^1 e^{-\lambda x} x^{j - 1} (1 - x)^{\alpha - j} \;\mathrm{d} x.\]

Next note that since \((1-x)^{\alpha-j} \leq 1\), then \[\int_0^1 e^{-\lambda x} x^{j - 1}(1 - x)^{\alpha - j} \;\mathrm{d} x \leq \int_0^1 e^{-\lambda x} x^{j - 1} \;\mathrm{d} x = \lambda^{-j} \bigl((j-1)! - \Gamma(j, \lambda)\bigr) \leq \lambda^{-j} (j-1)!\] where \(\Gamma(a, z)\) denotes the incomplete gamma function.

Hence \(M_j (\lambda)\) is upper bounded by \(\left({\gamma(c)}/{\lambda}\right)^j \binom{\alpha + 1}{j} \frac{1}{(\alpha-j)!}\). We next seek a lower bound on \(M_j (\lambda)\). First note that \(\lambda = \Omega\left((\log n)^2\right)\) and that \(j = O(\log n)\). Hence for all \(n\) sufficiently large, \(j \lambda^{-1} \in (0, 1)\) and therefore for \(x \in \left[0, j \lambda^{-1}\right]\) it follows that \(1 - x \geq 1 - j \lambda^{-1}\).

We therefore have that, for all \(n\) sufficiently large, \[\begin{align} \int_0^1 e^{-\lambda x} x^{j - 1}(1 - x)^{\alpha - j} \;\mathrm{d} x &\geq \int_0^{j \lambda^{-1}} e^{-\lambda x} x^{j - 1} \left(1 - j \lambda^{-1}\right)^{\alpha - j} \;\mathrm{d} x \\ &= \left(1 - j \lambda^{-1}\right)^{\alpha-j} \lambda^{-j} \bigl((j-1)! - \Gamma(j, j)\bigr). \end{align}\]

For all \(n\) sufficiently large, we have that \(\lambda > \frac{\varepsilon}{200 p_{\min}} (\log_{d-1} n) (\log n)\). Together with the fact that \(j \leq \alpha \leq ({4}/{p_{\min}}) \log_{d - 1} n\), we have that for sufficiently large \(n\), \[\left(1-j \lambda^{-1}\right)^{\alpha - j} \geq \left(1 - \frac{\left({800}/{\varepsilon}\right)}{\log n}\right)^{({4}/{p_{\min}}) \log_{d-1} n} \geq e^{-\frac{6400}{\varepsilon p_{\min}}}.\]

We also have that the term \((j-1)! - \Gamma(j, j)\) is lower bounded by \(\frac{(j-1)!}{2}\). Let \(\theta \mathrel{\vcenter{:}}= \frac{1}{2} e^{-\frac{6400}{\varepsilon p_{\min}}}\). Then \(M_j (\lambda)\) is lower bounded by \(\theta \left({\gamma(c)}/{\lambda}\right)^j\binom{\alpha + 1}{j}\frac{1}{(\alpha - j)!}\). Next note that, for all \(n\) sufficiently large, \[\begin{align} M_j (\lambda) - M_{j+1}(\lambda) &\geq \frac{\theta}{(\alpha-j)!} \left(\frac{\gamma(c)}{\lambda}\right)^j \binom{\alpha + 1}{j} - \left(\frac{\gamma(c)}{\lambda}\right)^{j+1} \frac{1}{(\alpha-j-1)!} \binom{\alpha + 1}{j+1} \nonumber \\ &= \frac{1}{(\alpha-j)!} \left(\frac{\gamma(c)}{\lambda}\right)^j \binom{\alpha + 1}{j} \left(\theta - \frac{\gamma(c) (\alpha-j)(\alpha-j+1)}{\lambda(j+1)}\right) \nonumber \\ &\geq \frac{1}{(\alpha-j)!} \left(\frac{\gamma(c)}{\lambda}\right)^j \binom{\alpha + 1}{j} \left(\theta - \gamma(c) \left(\frac{1600 ({4}/{p_{\min}} + {1}/{(\log n)})}{\varepsilon}\right)\right) \nonumber \\ &\geq \frac{1}{(\alpha-j)!} \left(\frac{\gamma(c)}{\lambda}\right)^j \binom{\alpha + 1}{j} \left(\theta - \gamma(c) \left(\frac{12800}{\varepsilon p_{\min}}\right)\right) \label{eq:sil5}. \end{align}\tag{37}\] and hence for \(M_j (\lambda) - M_{j+1}(\lambda) \geq 0\) we require that \(\theta \geq \gamma(c) \left(\frac{12800}{\varepsilon p_{\min}}\right)\).

Substituting for \(\theta\) and \(\gamma(c)\) then re-arranging, we require that \[\label{eq:sil6} e^{c \left({\varepsilon}/{2}\right)} \geq C \left(\frac{25600}{\varepsilon p_{\min}}\right)e^{\frac{6400}{\varepsilon p_{\min}}}.\tag{38}\]

In particular, there exists \(c > 0\) such that (38 ) is satisfied and hence \(M_j (\lambda) > M_{j+1}(\lambda)\) for all \(1 \leq j \leq \alpha - 1\) by (37 ). Therefore, for this choice of \(c\), together with (36 ) we have that \[\label{eq:sil7} \int_{\mathcal{K}_{\alpha}} \prod_{i = 0}^\alpha \left(1 - C e^{-(\mu_0 / 2) \delta - \lambda x_i}\right) \;\mathrm{d} \overrightarrow{x} \geq M_0 (\lambda) - M_1 (\lambda) - M_{\alpha + 1} (\lambda).\tag{39}\]

Now, \(M_0 (\lambda) = \frac{1}{\alpha!}\), \(M_1 (\lambda) \leq \frac{\gamma(c)}{\lambda} \frac{\alpha + 1}{(\alpha - 1)!} = \frac{1}{\alpha!} \left(\gamma(c)\lambda^{-1} \alpha (\alpha + 1)\right)\) and \(M_{\alpha + 1} (\lambda) = \frac{1}{\alpha!} \frac{\left(\gamma(c)\right)^{\alpha + 1}}{e^\lambda}\). Since \(\gamma(c)\) is a constant independent of \(n\), \(\alpha = \Theta(\log n)\) and \(\lambda = \Omega\left((\log n)^2\right)\), it follows that \(M_{\alpha + 1} (\lambda) = \frac{o(1)}{\alpha!}\). In particular then, for \(n\) sufficiently large, we have that \[\begin{align} M_0 (\lambda) - M_1 (\lambda) - M_{\alpha + 1} (\lambda) &\geq \frac{1}{\alpha!} \left(1 - \frac{\gamma(c) \alpha (\alpha + 1)}{\lambda} - o_n(1)\right) \nonumber \\ &\geq \frac{1}{\alpha!} \left(1 - o_n(1) - \gamma(c) \left(\frac{12800}{\varepsilon p_{\min}}\right)\right) \nonumber \\ &\geq \frac{1}{\alpha!} \left(\frac{1}{4} + \left(\theta - \gamma(c) \left(\frac{12800}{\varepsilon p_{\min}}\right)\right)\right) \nonumber \\ &\geq \frac{1}{4} \frac{1}{\alpha!} \label{eq:sil8} \end{align}\tag{40}\] where the first inequality follows from our bounds on each term, the second inequality follows from \(\alpha \leq ({4}/{p_{\min}}) \log_{d-1} n\) and \(\lambda > \frac{\varepsilon}{200 p_{\min}} (\log_{d-1} n)(\log n)\), the third inequality follows from the fact that \(\theta < \frac{1}{2} < \frac{3}{4} - o_n(1)\) for \(n\) sufficiently large, and the last inequality follows from our previous remark that our choice of \(c\) is such that \(\theta \geq \gamma(c) \left(\frac{12800}{\varepsilon p_{\min}}\right)\). The result follows from (33 ), (39 ) and (40 ). ◻

Proof. First note that \(\frac{\partial}{\partial x} f_\alpha(x, y) = \log\left(\frac{a(\alpha - x - y)}{x(1-a-b)}\right)\) and \(\frac{\partial}{\partial y} f_\alpha(x, y) = \log\left(\frac{b(\alpha - x - y)}{y(1-a-b)}\right)\). Both of these are zero at \((x, y) = \left(a \alpha, b \alpha\right)\). Hence (i) follows.

Let \(c = 1 - a - b\) and define \(h_\alpha(x, y) \mathrel{\vcenter{:}}= f_\alpha\left(a \alpha, b \alpha\right) - f_\alpha\left(a (\alpha + x), b (\alpha + y)\right)\). We will show that, given \(\alpha\) sufficiently large, for all \(0 \leq x, y \leq \sqrt{\alpha}\) we have that \(h_\alpha (x, y) \leq h_\alpha (\sqrt{\alpha}, \sqrt{\alpha})\). It suffices to show that \(\left(\frac{\partial}{\partial x} h_\alpha\right) (x, y) \geq 0\) and \(\left(\frac{\partial}{\partial y} h_\alpha\right) (x, y) \geq 0\) over the region \(0 \leq x, y \leq \sqrt{\alpha}\). First, observe that, for all \(\alpha\) sufficiently large, we have that for all \(0 \leq x, y \leq \sqrt{\alpha}\):

i. \(\left(\frac{\partial^2}{\partial x \partial x} h_\alpha\right) (x, y) = \frac{a}{\alpha + x} + \frac{a^2}{c \alpha - a x - by} > 0\) and \(\left(\frac{\partial^2}{\partial y \partial y} h_\alpha\right) (x, y) = \frac{b}{\alpha + y} + \frac{b^2}{c \alpha - a x - by} > 0\);

ii. \(\left(\frac{\partial^2}{\partial x \partial y} h_\alpha\right) (x, y) = \frac{a b}{c \alpha - a x - by} > 0\).

Also, \[\begin{align} \left(\frac{\partial}{\partial x} h_\alpha\right) (x, y) &= a \left( \log\left(\frac{c}{c \alpha - a x - b y}\right) - \log\left(\frac{1}{\alpha + x}\right)\right) \\ \mathrm{and} \quad \left(\frac{\partial}{\partial y} h_\alpha\right) (x, y) &= b \left(\log\left(\frac{c}{c \alpha - a x - b y}\right) - \log\left(\frac{1}{\alpha + y}\right)\right) \end{align}\] which are both \(0\) at \((x, y) = (0, 0)\). Hence, in conjunction with the second-order derivatives, we have that for \(\alpha\) sufficiently large then \(\left(\frac{\partial}{\partial x} h_\alpha\right) (x, y) \geq 0\) and \(\left(\frac{\partial}{\partial y} h_\alpha\right) (x, y) \geq 0\) over the region \(0 \leq x, y \leq \sqrt{\alpha}\), and consequently \(h_\alpha (x, y) \leq h_\alpha (\sqrt{\alpha}, \sqrt{\alpha})\) over this region.

All that remains to prove (ii) is to show that for \(\alpha\) sufficiently large, \(h_\alpha \left(\sqrt{\alpha}, \sqrt{\alpha}\right) \leq \frac{a+b}{2(1-a-b)}\). Consider the function \[g(z) = \frac{(1-c)^2 \left((1-c + cz) \log \left(1+\frac{c z}{1-c}\right)+ c(1-z) \log (1-z)\right)}{c^2 z^2}\] where, after some simple algebraic manipulation, we have that \[\begin{align} h_\alpha (\sqrt{\alpha}, \sqrt{\alpha}) &= \sqrt{\alpha} \left(\left(1+\sqrt{\alpha}\right) (1-c) \log \left(1+\frac{1}{\sqrt{\alpha}}\right)+\left(c\sqrt{\alpha} + c - 1\right) \log \left(1-\frac{1-c}{c \sqrt{\alpha}}\right)\right)\\ &= g\left(\frac{1-c}{c \sqrt{\alpha}}\right). \end{align}\]

From the Taylor expansion of \(g(z)\), we have that \(g(z) = \frac{1-c}{2c} + O(z)\) and therefore \(\lim\limits_{\alpha \to \infty} g\left(\frac{1-c}{c \sqrt{\alpha}}\right) = \frac{1-c}{2c}\). We also have that the Taylor expansion of \(g'(z)\) is given by \[g'(z) = \frac{1-2c}{6c} + \frac{(1-c)^2}{c}\sum_{k = 1}^\infty \frac{k-1}{k(k+1)}\left(1-\frac{c^{k+2}}{(c-1)^{k+2}}\right)z^k\] which one can readily check is negative for \(z\) sufficiently small given \(\frac{1}{2} < c < 1\). In particular there exists \(\alpha_0 > 0\) such that for all \(\alpha > \alpha_0\) the function \(g\left(\frac{1-c}{c \sqrt{\alpha}}\right)\) is increasing. Therefore for all \(\alpha > \alpha_0\), \(g\left(\frac{1-c}{c \sqrt{\alpha}}\right) < \frac{1-c}{2c}\) and hence (ii) follows. ◻

Proof. For any \(Z \sim \mathsf{Poisson}(T)\) for some \(T > 0\), it is well known (see e.g. Proposition 2.10 in [17]) that for any \(x > 0\), \(\mathbb{P}\left[\left|Z - T\right| \geq x\right] \leq 2 \exp\left(-\frac{x^2}{2(T + x)}\right)\). Fix \(T = \frac{k_{\min}+ k_{\max}}{2}\) and \(x = \frac{k_{\max}- k_{\min}}{2}\); observe that \(C_{\min}\log n \leq T \leq C_{\max}\log n\) and \(\left({C_{\mathrm{mid}}}/{2}\right) \log n \leq x \leq \left({C_{\max}}/{2}\right) \log n\).

Letting \(C \mathrel{\vcenter{:}}= \frac{C_{\mathrm{mid}}^2}{12 C_{\max}}\), since \(Y\) has rate 1 then \(N_Y(T)\) is distributed as \(\mathsf{Poisson}(T)\) and hence \[\mathbb{P} \left[k_{\min}\leq N_Y (T) \leq k_{\max}\right] \geq 1 - \mathbb{P}\left[\left|N_Y (T) - T\right| \geq x\right] \geq 1 - 2n^{-C} \geq \frac{1}{2}\] where the last inequality follows holds for all \(n\) sufficiently large, as required. ◻