How fast does the range of simple random walk grow?
February 11, 2026
Abstract
Consider a discrete-time simple random walk \((X_t)_{t\ge 0}\) on an infinite, connected, locally finite simple graph \(G\), and let \[R_t := |\{X_0,\ldots,X_t\}|\] denote its range. The main result of this revised note is that positive vertex isoperimetry already forces linear expected range, with no bounded-degree assumption: if \[\iota_V(G) := \inf_{0<|S|<\infty} \frac{|\partial_V S|}{|S|} >0,\] then \(\mathbb{E}_x R_t \ge c(G)(t+1)\) for every starting vertex \(x\) and every \(t\ge 0\). The proof is direct: vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex. We also record a finite counterpart: in an \(n\)-vertex finite vertex expander, the expected hitting time of an independent stationary random target is \(\Theta(n)\), again with no restriction on degrees.
We also record a chain of geometrically growing lollipops for which \[\mathbb{E}_o R_t \asymp t^{1/3},\] so the subdiffusive exponent \(1/3\) need not be accompanied by superdiffusive oscillations. In particular, for this graph the lower and upper logarithmic exponents of \(\mathbb{E}_oR_t\) are both equal to \(1/3\). Finally, since Barnes and Feige proved the sharp universal estimate \(\mathbb{E}T_n= O(n^3)\) for the \(n\)-th discovery time, we move our elementary proof of the weaker bound \(\mathbb{E}T_n=O(n^3\log n)\) to a later section as a short self-contained argument with a logarithmic loss. We close with a related bounded-degree mixing statement: if the lazy walk has worst-case mixing time \(m\), then at least \(c\sqrt m\) starting vertices are still noticeably unmixed at time \(\lfloor m/2\rfloor\). This final result uses the same commute-time/effective-resistance control of connected sets that appears throughout the paper.
1 Setup and main result↩︎
Throughout, \(G=(V,E)\) is an infinite, connected, locally finite, simple graph. The simple random walk \((X_t)_{t\ge 0}\) has transition matrix \[P(x,y)=\frac{1}{\operatorname{deg}(x)}\mathbf{1}_{\{x,y\}\in E}.\] For \(A\subseteq V\), write \[\tau_A:=\inf\{t\ge 0:X_t\in A\}, \qquad \tau_x^+:=\inf\{t\ge 1:X_t=x\}.\] The range and discovery times are \[R_t:=|\{X_0,\ldots,X_t\}|, \qquad T_n:=\inf\{t\ge 0:R_t=n\}.\] For a finite set \(S\subset V\), define its outer vertex boundary by \[\partial_V S:=\{x\in V\setminus S:\exists y\in S \textrm{ with } x\sim y\},\] and put \[\iota_V(G):=\inf_{0<|S|<\infty}\frac{|\partial_V S|}{|S|}.\] The main point is that vertex nonamenability alone, even with unbounded degrees, implies the uniform transience needed for linear range.
Theorem 1 (Vertex nonamenability implies linear range). Assume that \(\iota:=\iota_V(G)>0\). Then, for every starting vertex \(x\in V\) and every \(t\ge 0\), \[\mathbb{E}_x R_t \ge \kappa(\iota)(t+1),\] where one may take \[\kappa(\iota):=\frac{1}{8} \min\left\{1,\frac{1}{2}\left(\sqrt{1+\iota}-1\right)^2\right\}.\] Equivalently, \(G\) has linear expected range.
On bounded-degree graphs, vertex nonamenability is classically equivalent to a spectral gap for the random-walk operator, and hence to uniform exponential decay of return probabilities. The theorem above avoids that route and uses the vertex boundary directly. The simplicity assumption is important: for multigraphs, vertex boundary is insensitive to edge multiplicities.
2 Consequences of vertex expansion↩︎
2.1 The infinite case: proof of Theorem 1.1↩︎
For finitely supported \(f:V\to\mathbb{R}\), define the unweighted Dirichlet energy \[\mathcal{E}(f):=\sum_{\{u,v\}\in E} \left(f(u)-f(v)\right)^2, \qquad \|f\|_2^2:=\sum_{v\in V} f(v)^2.\]
Lemma 1 (A Dirichlet inequality from vertex expansion). If \(\iota_V(G)=\iota>0\), then every finitely supported \(f:V\to\mathbb{R}\) satisfies \[\mathcal{E}(f)\ge a(\iota)\|f\|_2^2, \qquad a(\iota):=\frac{1}{2}\left(\sqrt{1+\iota}-1\right)^2.\]
Proof. By replacing \(f\) with \(|f|\), we may assume that \(f\ge 0\), since this does not increase \(\mathcal{E}(f)\). For \(y\in V\), let \[Mf(y):=\max_{z\sim y} f(z), \qquad d(y):=(Mf(y)-f(y))_+.\] For \(s\ge 0\), set \(A_s:=\{v:f(v)^2>s\}\). Since \(A_s\) is finite, the isoperimetric assumption and the layer-cake formula give \[\iota\|f\|_2^2 = \iota\int_0^\infty |A_s|\,ds \le \int_0^\infty |\partial_V A_s|\,ds = \sum_{y\in V} \left((Mf(y))^2-f(y)^2\right)_+.\] But \[\left((Mf(y))^2-f(y)^2\right)_+ = d(y)(Mf(y)+f(y))=2f(y)d(y)+d(y)^2.\] Moreover, \[\sum_y d(y)^2 \le \sum_y\sum_{z\sim y} (f(z)-f(y))^2 = 2\mathcal{E}(f).\] Consequently, \[\iota\|f\|_2^2 \le 2\|f\|_2\left(\sum_y d(y)^2\right)^{1/2}+\sum_y d(y)^2 \le 2\sqrt{2\mathcal{E}(f)}\,\|f\|_2+2\mathcal{E}(f).\] If \(\|f\|_2=0\) there is nothing to prove. Otherwise, with \(r:=\sqrt{\mathcal{E}(f)}/\|f\|_2\), the last display gives \[\iota\le 2\sqrt2\,r+2r^2.\] Solving the resulting quadratic inequality yields \[r^2\ge \frac{1}{2}\left(\sqrt{1+\iota}-1\right)^2,\] which is the claim. ◻
We now convert the global inequality into a pointwise escape estimate. For a vertex \(x\), define its electrical capacity by \[\operatorname{Cap}(x):=\inf\{\mathcal{E}(f): f \textrm{ is finitely supported and } f(x)=1\}.\] With our convention for \(\mathcal{E}\), the standard network identity is \[\operatorname{Cap}(x)=\operatorname{deg}(x)\mathbb{P}_x(\tau_x^+=\infty).\]
Lemma 2 (Uniform escape from points). Under the assumptions of Theorem 1.1, for every \(x\in V\), \[\mathbb{P}_x(\tau_x^+=\infty)\ge \kappa(\iota).\]
Proof. Let \(D:=\operatorname{deg}(x)\), and let \(f\) be finitely supported with \(f(x)=1\). By truncating \(f\) to \([0,1]\), we may assume \(0\le f\le 1\) without increasing \(\mathcal{E}(f)\).
If at least \(D/2\) neighbours \(y\sim x\) satisfy \(f(y)\le 1/2\), then the edges incident to \(x\) give \[\mathcal{E}(f)\ge \frac{D}{2}\left(\frac{1}{2}\right)^2=\frac{D}{8}.\] Otherwise, at least \(D/2\) neighbours satisfy \(f(y)>1/2\), and hence \[\|f\|_2^2\ge \frac{D}{2}\left(\frac{1}{2}\right)^2=\frac{D}{8}.\] By Lemma 2.1, this implies \[\mathcal{E}(f)\ge a(\iota)\frac{D}{8}.\] Thus every admissible \(f\) satisfies \[\mathcal{E}(f)\ge \frac{1}{8}\min\{1,a(\iota)\}\operatorname{deg}(x)=\kappa(\iota)\operatorname{deg}(x).\] Taking the infimum over \(f\) gives \(\operatorname{Cap}(x)\ge \kappa(\iota)\operatorname{deg}(x)\), and the capacity identity gives the desired escape estimate. ◻
Proof of Theorem 1.1. Each visited vertex has a unique last visit before time \(t\), so \[R_t=\sum_{s=0}^t \mathbf{1}_{\{X_s\notin\{X_{s+1},\ldots,X_t\}\}}.\] Conditioning on the past up to time \(s\) and using Lemma 2.2, \[\begin{align} &\mathbb{P}_x\left(X_s\notin\{X_{s+1},\ldots,X_t\}\mid X_0,\ldots,X_s\right) \\ &\qquad = \mathbb{P}_{X_s}(\tau_{X_s}^+>t-s) \ge \mathbb{P}_{X_s}(\tau_{X_s}^+=\infty) \ge \kappa(\iota). \end{align}\] Summing over \(s=0,\ldots,t\) gives \[\mathbb{E}_x R_t\ge \kappa(\iota)(t+1).\] ◻
2.2 Finite vertex expanders and stationary targets↩︎
We record the finite analogue in a form which is useful for graphs with unbounded degrees. Let \(G=(V,E)\) now be a finite, connected, simple graph with \(n:=|V|\ge 2\) and \(M:=|E|\). Write \[\pi(x):=\frac{\operatorname{deg}(x)}{2M}\] for the stationary measure of simple random walk, and define the finite vertex-expansion constant \[\iota_{1/2}(G):=\min_{\substack{\emptyset\ne S\subseteq V\\ |S|\le n/2}}\frac{|\partial_V S|}{|S|}.\] If \(Y\) is an independent random vertex with law \(\pi\), then \(\tau_Y\) denotes the first hitting time of this random target, with the convention \(\tau_x=0\) when the walk starts at \(x\).
Theorem 2 (Finite stationary-target bound). Let \(G\) be as above and assume that \(\iota_{1/2}(G)\ge \iota>0\). Then, for every starting vertex \(x\in V\), \[\frac{n-1}{2}\le \mathbb{E}_x\tau_Y\le \frac{4}{\kappa(\iota)}n,\] where \(\kappa(\iota)\) is the constant from Theorem 1.1. In particular, on finite vertex expanders, the hitting time of a typical vertex sampled from stationarity is of order \(n\), uniformly over the degrees.
Proof. We first note the finite version of Lemma 2.1. If \(f:V\to\mathbb{R}\) is supported on a set of size at most \(n/2\), then the proof of Lemma 2.1 applies verbatim, because every level set \(\{v:f(v)^2>s\}\) also has size at most \(n/2\). Thus \[\mathcal{E}(f)\ge a(\iota)\|f\|_2^2, \qquad a(\iota)=\frac{1}{2}\left(\sqrt{1+\iota}-1\right)^2.\] Consequently, the proof of Lemma 2.2 gives the following localized point estimate: if \(f\) is supported on a set of size at most \(n/2\) and \(f(z)=1\), then \[\mathcal{E}(f)\ge \kappa(\iota)\operatorname{deg}(z). \] Fix two vertices \(x,y\). For \(x=y\) there is nothing to prove in the resistance estimate below, so assume \(x\ne y\). Truncating an arbitrary unit potential to \([0,1]\) only decreases its energy, so it suffices to consider \(\phi:V\to[0,1]\) satisfying \(\phi(x)=1\) and \(\phi(y)=0\). Set \[A:=\{v:\phi(v)\ge 1/2\}.\] If \(|A|\le n/2\), apply (*) to \(h=(2\phi-1)_+\). Then \(h(x)=1\), \(h\) is supported on \(A\), and \(\mathcal{E}(h)\le 4\mathcal{E}(\phi)\), so \[\mathcal{E}(\phi)\ge \frac{\kappa(\iota)}{4}\operatorname{deg}(x).\] If \(|A|>n/2\), apply (*) instead to \(h=(1-2\phi)_+\), which is supported on \(V\setminus A\), satisfies \(h(y)=1\), and obeys \(\mathcal{E}(h)\le 4\mathcal{E}(\phi)\). This gives \[\mathcal{E}(\phi)\ge \frac{\kappa(\iota)}{4}\operatorname{deg}(y).\] Therefore every unit potential between \(x\) and \(y\) has energy at least \[\frac{\kappa(\iota)}{4}\min\{\operatorname{deg}(x),\operatorname{deg}(y)\}.\] By Dirichlet’s principle, \[\operatorname{R}_{\mathrm{eff}}(x,y)\le \frac{4}{\kappa(\iota)\min\{\operatorname{deg}(x),\operatorname{deg}(y)\}}.\] The commute-time identity then yields, for \(x\ne y\), \[H(x,y)+H(y,x)=2M\operatorname{R}_{\mathrm{eff}}(x,y) \le \frac{8M}{\kappa(\iota)\min\{\operatorname{deg}(x),\operatorname{deg}(y)\}}.\] The same upper bound is trivially true when \(x=y\) if the left-hand side is interpreted as zero. Let \(X,Y\) be independent with law \(\pi\). Averaging the last display gives \[\begin{align} \mathbb{E}[H(X,Y)+H(Y,X)] &\le \frac{8M}{\kappa(\iota)} \sum_{x,y\in V}\pi(x)\pi(y)\frac{1}{\min\{\operatorname{deg}(x),\operatorname{deg}(y)\}} \\ &= \frac{2}{\kappa(\iota)M} \sum_{x,y\in V}\max\{\operatorname{deg}(x),\operatorname{deg}(y)\} \\ &\le \frac{2}{\kappa(\iota)M} \sum_{x,y\in V}\bigl(\operatorname{deg}(x)+\operatorname{deg}(y)\bigr) =\frac{8n}{\kappa(\iota)}. \end{align}\] By the random target lemma, also known as Kemeny’s constant identity, the quantity \[K(G):=\sum_{y\in V}\pi(y)H(x,y)=\mathbb{E}_x\tau_Y\] is independent of \(x\). Hence the left-hand side of the preceding averaged inequality equals \(2K(G)\), and so \[\mathbb{E}_x\tau_Y=K(G)\le \frac{4n}{\kappa(\iota)}.\] For the lower bound, use the spectral form of Kemeny’s constant. If \(1=\lambda_1>\lambda_2\ge\cdots\ge\lambda_n\ge -1\) are the eigenvalues of the reversible transition matrix, then \[K(G)=\sum_{i=2}^n \frac{1}{1-\lambda_i}.\] Each summand is at least \(1/2\), whence \(K(G)\ge (n-1)/2\). ◻
Remark 3. The stationary averaging is essential. A finite vertex expander need not satisfy \(H(x,y)=O(n)\) for every fixed target \(y\); for example, a complete graph with one leaf attached to each clique vertex is still a vertex expander, but hitting a specified leaf can take order \(n^2\). The ingredients in Theorem 2.3 are classical: the random target lemma and the commute-time/effective-resistance identity. The point here is that vertex expansion supplies the required resistance bound without any degree hypothesis; see, for example, [1]–[3].
3 A lollipop chain with no superdiffusive oscillations↩︎
Barnes and Feige proved that, uniformly over all finite or infinite connected graphs and all starting vertices, the expected time to discover \(n\) distinct vertices is \(O(n^3)\) [4], [5]. Equivalently, there is a universal constant \(c>0\) such that \[\mathbb{E}_x R_t\ge ct^{1/3},\qquad t\ge 1.\] The following example shows that this universal exponent can be exact at all large scales, not merely along selected subsequences.
Theorem 4 (No forced oscillation above \(1/2\)). There is an infinite, connected, locally finite simple graph \(G\) and a vertex \(o\) such that, for some constants \(0<c<C<\infty\), \[ct^{1/3}\le \mathbb{E}_oR_t\le Ct^{1/3},\qquad t\ge 1.\] Consequently, if \[\alpha:=\liminf_{t\to\infty}\frac{\log \mathbb{E}_oR_t}{\log t}, \qquad \beta:=\limsup_{t\to\infty}\frac{\log \mathbb{E}_oR_t}{\log t},\] then \(\alpha=\beta=1/3\).
Thus subdiffusive range along some time scales does not force superdiffusive range along others; in particular, \(\alpha=1/3\) does not imply \(\beta=1\).
For \(m\ge 2\), let \(L_m\) be the lollipop obtained from a clique of size \(m\) by choosing one clique vertex \(a\), attaching to it a path \[a=p_0\sim p_1\sim\cdots\sim p_m=b.\] Thus \(|L_m|=2m\). Figure 1 shows the case \(m=5\).
We will use the following standard estimate for crossing a lollipop quickly.
Lemma 3 (Fast crossing of a lollipop is unlikely). There is a universal constant \(C_0<\infty\) such that, for every \(m\ge 2\) and every \(t\ge 0\), \[\mathbb{P}_a^{L_m}(\tau_b\le t)\le C_0\min\left\{1,\frac{t}{m^3}\right\}.\]
Proof. We recall the usual lollipop estimate. A crossing from \(a\) to \(b\) can occur only during an excursion which first steps from \(a\) to \(p_1\) and then reaches \(p_m\) before returning to \(p_0\). The expected number of such path excursions begun by time \(t\) is at most \[C\left(1+\frac{t}{m^2}\right).\] Indeed, visits to the gateway \(a\) occur on the \(m\) scale inside the clique, and at each such visit the probability to choose the unique path edge is \(1/m\); suppressing path excursions can only increase the number of attempts, and gives the displayed renewal bound.
For one path excursion, the gambler’s-ruin probability of reaching \(p_m\) before \(p_0\) is \(1/m\). The time-restricted version satisfies \[q_m(u):=\mathbb{P}_1(\tau_m\le u,\tau_m<\tau_0) \le C\min\left\{\frac{u}{m^3},\frac{1}{m}\right\},\] for simple random walk on the interval \(\{0,1,\ldots,m\}\) started from \(1\). This follows, for example, from the standard spectral expansion of the walk killed on \(\{0,m\}\), since the first-hit density at \(m\) is bounded by \(C/m^3\) up to the diffusive scale \(m^2\) and its total mass is \(1/m\).
By the strong Markov property and a union bound over the path excursions begun before time \(t\), \[\mathbb{P}_a^{L_m}(\tau_b\le t) \le C\left(1+\frac{t}{m^2}\right)\min\left\{\frac{t}{m^3},\frac{1}{m}\right\} \le C_0\min\left\{1,\frac{t}{m^3}\right\}.\] The last inequality is immediate by considering separately \(t\le m^2\), \(m^2<t\le m^3\), and \(t>m^3\). ◻
Proof of Theorem 3.1. Let \(m_k:=2^k\). Take disjoint copies \(L_{m_k}\), with distinguished endpoints \(a_k,b_k\), and add the single edge \[b_k\sim a_{k+1},\qquad k\ge 1.\] Let \(G\) be the resulting infinite graph and start the walk from \(o=a_1\).
The lower bound \(\mathbb{E}_oR_t\ge ct^{1/3}\) is exactly the Barnes–Feige universal estimate. We prove the matching upper bound. Let \(\sigma_k\) be the first hitting time of the block \(L_{m_k}\). Since vertices in \(L_{m_k}\) can be visited only after \(\sigma_k\), \[\mathbb{E}_oR_t\le \sum_{k\ge 1} |L_{m_k}|\mathbb{P}_o(\sigma_k\le t) \le 2\sum_{k\ge 1} m_k\mathbb{P}_o(\sigma_k\le t).\] Choose \(K=K(t)\) such that \[m_K^3\le t < m_{K+1}^3.\] The contribution of the first \(K+2\) blocks is bounded by \[2\sum_{k\le K+2} m_k\le Cm_K\le Ct^{1/3}.\] For \(k\ge K+3\), reaching \(L_{m_k}\) by time \(t\) requires crossing the previous lollipop \(L_{m_{k-1}}\) from \(a_{k-1}\) to \(b_{k-1}\) within time \(t\). By the strong Markov property and Lemma 3.2, \[\mathbb{P}_o(\sigma_k\le t)\le C\frac{t}{m_{k-1}^3}.\] Therefore the tail contribution is at most \[Ct\sum_{k\ge K+3}\frac{m_k}{m_{k-1}^3}.\] Since \(m_k=2^k\), we have \(m_k/m_{k-1}^3\asymp 2^{-2k}\), and so \[t\sum_{k\ge K+3}\frac{m_k}{m_{k-1}^3} \le Ct2^{-2K}\le Cm_K\le Ct^{1/3}.\] This proves \(\mathbb{E}_oR_t\le Ct^{1/3}\) and completes the proof. ◻
4 A self-contained universal estimate with a logarithmic loss↩︎
Barnes and Feige’s theorem gives the optimal universal discovery-time estimate \(\mathbb{E}T_n=O(n^3)\) [4], [5]. The argument below is a short, self-contained proof of the weaker bound \(\mathbb{E}T_n=O(n^3\log n)\). It is included only for completeness and for comparison with the sharp result.
For \(n\ge 1\), define the maximal edge density and minimal volume growth by \[f(n):=\max_{\substack{S\subseteq V\\ |S|=n}} |E_S|, \qquad g(n):=\min_{x\in V} |B(x,n)|,\] where \(E_S\) is the set of edges with both endpoints in \(S\), and \[B(x,r):=\{y\in V:\operatorname{dist}(x,y)\le r\}.\]
Theorem 5 (Elementary discovery-time bound). For every \(n\ge 1\), \[\mathbb{E}T_n\le 4nf(n)\sum_{r=0}^{n-1}\frac{1}{g(r)}.\]
Corollary 1 (Universal bound with logarithmic loss). There is a universal constant \(C<\infty\) such that, for every infinite connected locally finite graph and every \(n\ge 2\), \[\mathbb{E}T_n\le Cn^3\log n.\] Consequently, there is a universal constant \(c>0\) such that, for all \(t\ge 2\), \[\mathbb{E}R_t\ge c\left(\frac{t}{\log t}\right)^{1/3}.\]
Proof. Since \(f(n)\le \binom{n}{2}\) and \(g(r)\ge r+1\), Theorem 4.1 gives \(\mathbb{E}T_n\le Cn^3\log n\). To convert this to a range estimate, fix \(t\ge 2\) and choose \[n:=\left\lfloor \left(\frac{t}{C'\log t}\right)^{1/3}\right\rfloor\] with \(C'\) sufficiently large. Since \(\{R_t<n\}=\{T_n>t\}\) up to the harmless convention at equality, Markov’s inequality gives \[\mathbb{P}(R_t<n)\le \frac{\mathbb{E}T_n}{t}\le \frac{1}{2}.\] Thus \(\mathbb{E}R_t\ge n\mathbb{P}(R_t\ge n)\ge n/2\), after adjusting constants. ◻
Corollary 2 (Uniform polynomial growth). Assume that, for some \(d>1\), there are constants \(0<a\le A<\infty\) such that, for every vertex \(x\) and every \(r\ge 1\), \[ar^d\le |B(x,r)|\le Ar^d.\] Then there is a constant \(c>0\) such that, for every starting vertex \(x\) and every \(t\ge 1\), \[\mathbb{E}_xR_t\ge c(t+1)^{d/(d+1)}=c(t+1)^{1/2+\varepsilon}, \qquad \varepsilon=\frac{d-1}{2(d+1)}>0.\]
Proof. The upper volume bound at radius \(1\) gives a uniform degree bound. We first prove the estimate for the lazy walk \(\widetilde{X}\) and write \(\widetilde{R}_t\) for its range. The heat-kernel estimate of Barlow, Coulhon and Grigor’yan [6], applied with the lower volume bound \(|B(x,r)|\ge ar^d\), gives \[\sup_x \widetilde{\mathbb{P}}_x(\widetilde{X}_s=x) \le C(s+1)^{-d/(d+1)},\qquad s\ge 0.\] Consequently, \[\ell_*(t):=\sup_x\sum_{s=0}^t \widetilde{\mathbb{P}}_x(\widetilde{X}_s=x) \le C(t+1)^{1/(d+1)}.\] Let \(L_y(t):=\sum_{s=0}^t \mathbf{1}_{\{\widetilde{X}_s=y\}}\) and let \(T_y\) be the first hitting time of \(y\). By the Markov property, \[\widetilde{\mathbb{E}}_x L_y(t) \le \widetilde{\mathbb{P}}_x(T_y\le t)\,\ell_*(t).\] Summing over \(y\) yields \[t+1=\sum_y \widetilde{\mathbb{E}}_x L_y(t) \le \ell_*(t)\,\widetilde{\mathbb{E}}_x\widetilde{R}_t,\] and hence \(\widetilde{\mathbb{E}}_x\widetilde{R}_t\ge c(t+1)^{d/(d+1)}\). Under the usual coupling, the lazy walk by time \(t\) has made at most \(t\) genuine simple-random-walk moves, so its range is contained in the non-lazy range up to time \(t\). This gives the claimed bound for simple random walk. In fact, the proof only uses the lower volume bound and bounded degree. ◻
It remains to prove Theorem 4.1. We use three elementary lemmas.
Lemma 4 (Time to hit a neighbour). On a finite connected graph \(H=(W,F)\), \[\max_{\{x,y\}\in F} \mathbb{E}_x\tau_y\le 2|F|-1.\]
Proof. Fix \(\{x,y\}\in F\). The return time \[\tau_y^+:=\inf\{t\ge 1:X_t=y\}\] satisfies the classical identity \[\mathbb{E}_y\tau_y^+=\frac{2|F|}{\operatorname{deg}(y)}.\] By the Markov property at time \(1\), \[\mathbb{E}_y\tau_y^+=1+\frac{1}{\operatorname{deg}(y)}\sum_{z\sim y}\mathbb{E}_z\tau_y \ge 1+\frac{\mathbb{E}_x\tau_y}{\operatorname{deg}(y)}.\] Combining the two displays yields \(\mathbb{E}_x\tau_y\le 2|F|-\operatorname{deg}(y)\le 2|F|-1\). ◻
Lemma 5 (Escape time from a finite set). For any finite set \(S\subset V\) and any \(x\in S\), \[\mathbb{E}_x\tau_{S^c}\le (2|E_S|+1)\operatorname{dist}(x,S^c).\]
Proof. Choose a shortest path \(x=x_0,\ldots,x_r\) to \(S^c\). Thus \(r=\operatorname{dist}(x,S^c)\), \(x_1,\ldots,x_{r-1}\in S\), and \(x_r\notin S\). Let \(H\) be the induced graph \(G[S]\), augmented by \(x_r\) and the edge \(\{x_{r-1},x_r\}\). We may couple SRW on \(G\) and SRW on \(H\) so that they coincide until the walk on \(G\) exits \(S\). Therefore, \[\mathbb{E}_x\tau_{S^c}\le \sum_{i=1}^r \mathbb{E}_{x_{i-1}}^H\tau_{x_i} \le (2|E_S|+1)r,\] where the last step follows from Lemma 4.4, since \(H\) has \(|E_S|+1\) edges. ◻
Lemma 6 (A deterministic packing bound). Let \(S_k:=\{X_{T_1},\ldots,X_{T_k}\}\) be the set of the first \(k\) discovered vertices. Then, for every \(n\ge 1\), \[\sum_{k=1}^n \operatorname{dist}(X_{T_k},S_k^c) \le 2n\sum_{r=0}^{\lfloor n/2\rfloor-1}\frac{1}{g(r)}.\]
Proof. Fix \(r\ge 0\) and define \[I(r):=\{k\in\{1,\ldots,n\}:\operatorname{dist}(X_{T_k},S_k^c)>r\}.\] If \(k\in I(2r)\) and \(j>k\), then \(\operatorname{dist}(X_{T_k},X_{T_j})>2r\). Hence the balls \(\{B(X_{T_k},r):k\in I(2r)\}\) are pairwise disjoint, and all are contained in \(S_n\). Therefore, \[|I(2r)|g(r)\le \sum_{k\in I(2r)} |B(X_{T_k},r)|\le n,\] so \(|I(2r)|\le n/g(r)\).
For each \(k\le n\), \[\begin{align} \operatorname{dist}(X_{T_k},S_k^c) &=\sum_{r=0}^{n-1}\mathbf{1}_{\{k\in I(r)\}} \\ &\le \sum_{r=0}^{\lfloor n/2\rfloor-1} \left(\mathbf{1}_{\{k\in I(2r)\}}+\mathbf{1}_{\{k\in I(2r+1)\}}\right) \\ &\le 2\sum_{r=0}^{\lfloor n/2\rfloor-1}\mathbf{1}_{\{k\in I(2r)\}}, \end{align}\] where the last inequality uses \(I(2r+1)\subseteq I(2r)\). Summing over \(k\) and using the bound on \(|I(2r)|\) proves the lemma. ◻
Proof of Theorem 4.1. For \(k\ge 1\), the strong Markov property at time \(T_k\) and Lemma 4.5 give \[\mathbb{E}[T_{k+1}-T_k\mid X_0,\ldots,X_{T_k}] =\mathbb{E}_{X_{T_k}}\tau_{S_k^c} \le (2|E_{S_k}|+1)\operatorname{dist}(X_{T_k},S_k^c).\] For \(k\le n-1\), we have \(|E_{S_k}|\le f(k)\) and hence \[2|E_{S_k}|+1\le 2f(k+1)\le 2f(n),\] where we used that every finite \(k\)-set in an infinite connected graph has an outside neighbour, so it can be enlarged to a \((k+1)\)-set with at least one additional edge; hence \(f(k+1)\ge f(k)+1\). Thus, for \(n\ge 2\), \[\mathbb{E}T_n\le 2f(n)\,\mathbb{E}\left[\sum_{k=1}^{n-1}\operatorname{dist}(X_{T_k},S_k^c)\right].\] The case \(n=1\) is trivial. Lemma 4.6 gives \[\mathbb{E}T_n\le 4nf(n)\sum_{r=0}^{\lfloor n/2\rfloor-1}\frac{1}{g(r)} \le 4nf(n)\sum_{r=0}^{n-1}\frac{1}{g(r)},\] as claimed. ◻
5 Many slow starting vertices at half the mixing time↩︎
The preceding sections relate random-walk time scales to the amount of space explored by the walk. The following bounded-degree mixing statement is in the same spirit: a large worst-case mixing time cannot be caused by a single isolated starting point, but must be witnessed by a connected set of slow starts of diffusive size. The proof again uses the commute-time/effective-resistance identity to convert the size of a connected set into an upper bound on the time needed to leave it.
Let \(G=(V,E)\) be a finite connected graph, and let \((X_t)_{t\ge 0}\) be lazy simple random walk on \(G\): \[P(x,x)=\frac{1}{2}, \qquad P(x,y)=\frac{1}{2\operatorname{deg}(x)}\quad (x\sim y).\] Write \(\pi\) for the stationary distribution and \[d_x(t):=\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}.\] For \(0<\varepsilon<1\), define \[t_{\mathrm{mix}}(x;\varepsilon):=\min\{t\ge 0:d_x(t)\le \varepsilon\}, \qquad t_{\mathrm{mix}}(x):=t_{\mathrm{mix}}(x;1/4),\] and \[t_{\mathrm{mix}}(G):=\max_{x\in V}t_{\mathrm{mix}}(x).\]
Theorem 6 (Buffered slow-start lower bound). Fix \(\Delta\ge 1\) and \(0<\eta<1/4\). There exists \(c=c(\Delta,\eta)>0\) such that the following holds. Let \(G\) be a finite connected graph of maximum degree at most \(\Delta\), and let lazy simple random walk on \(G\) satisfy \[t_{\mathrm{mix}}(G)=m.\] Then \[|\{x\in V:d_x(\lfloor m/2\rfloor)>\eta\}|\ge c\sqrt m.\] Equivalently, \[|\{x\in V:t_{\mathrm{mix}}(x;\eta)>\lfloor m/2\rfloor\}|\ge c\sqrt m.\]
We use two standard estimates. The first is the same resistance input as above, now applied after collapsing the complement of a connected set.
Lemma 7 (Exit from a connected set). Let \(G\) be a finite connected graph of maximum degree at most \(\Delta\). Let \(C\subsetneq V\) be connected and set \(s:=|C|\). For lazy simple random walk, define \[\tau_{C^c}:=\inf\{t\ge 0:X_t\notin C\}.\] Then \[\sup_{x\in C}\mathbb{E}_x\tau_{C^c}\le 4\Delta s^2.\]
Proof. First consider the non-lazy walk. Collapse \(C^c\) to a single boundary vertex \(\partial\): retain all edges inside \(C\) and add one edge from \(v\in C\) to \(\partial\) for each edge of \(G\) from \(v\) to \(C^c\). Until the first hit of \(\partial\), the walk in this collapsed network has the same law as the original non-lazy walk until it exits \(C\).
Let \(M_H\) be the number of edges in the collapsed graph \(H\). Since \[2|E(C)|+|E(C,C^c)|=\sum_{v\in C}\operatorname{deg}_G(v)\le \Delta s,\] we have \(M_H\le \Delta s\). For every \(x\in C\), the effective resistance from \(x\) to \(\partial\) is at most the graph distance from \(x\) to \(\partial\), and this distance is at most \(s\), because \(C\) is connected and has a vertex adjacent to \(C^c\). Hence the commute-time identity gives \[\mathbb{E}_x^{\mathrm{nonlazy}} T_\partial\le 2M_H\operatorname{R}_{\mathrm{eff}}(x,\partial)\le 2\Delta s^2.\] Laziness inserts independent geometric holding times of mean \(2\) before actual moves, so the lazy expected exit time is at most twice the non-lazy one. ◻
Lemma 8 (A global quadratic bound). There is a constant \(A_0=A_0(\Delta)<\infty\) such that every finite connected graph \(G\) of maximum degree at most \(\Delta\), with \(N:=|V|\), satisfies \[t_{\mathrm{mix}}(G)\le A_0N^2.\] Consequently, if \(t_{\mathrm{mix}}(G)=m\), then \[N\ge A_0(\Delta)^{-1/2}\sqrt m.\]
Proof. Let \[t_H(1/4):=\max_{x\in V}\max_{A\subseteq V:\pi(A)\ge 1/4}\mathbb{E}_x\tau_A.\] For lazy reversible finite chains, the hitting-time characterization of mixing times gives \[t_{\mathrm{mix}}(G)\le Kt_H(1/4)\] for a universal constant \(K\); see [7], [8]. If \(A\subseteq V\) is nonempty and \(a\in A\), then \(\tau_A\le \tau_a\). For non-lazy simple random walk, the commute-time identity gives, for all \(x,a\in V\), \[\mathbb{E}_x^{\mathrm{nonlazy}}\tau_a \le 2|E|\operatorname{R}_{\mathrm{eff}}(x,a)\le 2|E|\operatorname{dist}(x,a)\le \Delta N^2,\] using \(|E|\le \Delta N/2\) and \(\operatorname{dist}(x,a)\le N-1\). Laziness changes expected hitting times by at most a factor of \(2\), so \(t_H(1/4)\le 2\Delta N^2\), and the result follows with \(A_0(\Delta)=2K\Delta\). ◻
Proof of Theorem 5.1. The case \(m=0\) is harmless, so assume \(m\ge 1\). Set \[T:=\lfloor m/2\rfloor, \qquad B:=\{x\in V:d_x(T)>\eta\}.\] Choose \(x^*\) with \(t_{\mathrm{mix}}(x^*)=m\). Since \(T<m\), we have \(d_{x^*}(T)>1/4>\eta\), and hence \(x^*\in B\). Let \(C\) be the connected component of \(B\) containing \(x^*\), and write \(s:=|C|\).
If \(C=V\), then \(B=V\), and Lemma 5.3 gives \[|B|=|V|\ge A_0(\Delta)^{-1/2}\sqrt m.\] Thus assume that \(C\subsetneq V\). Let \[\tau:=\inf\{t\ge 0:X_t\notin C\}\] for the walk started from \(x^*\), and put \[r:=m-1-T.\] For \(m\ge 4\), one has \(r\ge m/4\); the finitely many cases \(m<4\) will be absorbed into the final constant.
On the event \(\{\tau\le r\}\), the exit vertex \(X_\tau\) lies outside \(B\): if it belonged to \(B\), then it would be adjacent to \(C\) and hence would be in the same connected component of \(B\). Thus \(d_{X_\tau}(T)\le \eta\). Since total-variation distance to stationarity is nonincreasing in time, \[d_{X_\tau}(u)\le \eta \qquad \textrm{for every } u\ge T.\] If \(\tau\le r\), then \(m-1-\tau\ge T\). By the Markov property, the law of \(X_{m-1}\) from \(x^*\) can therefore be decomposed as \[\mathcal{L}_{x^*}(X_{m-1})=\alpha\mu+(1-\alpha)\nu, \qquad \alpha:=\mathbb{P}_{x^*}(\tau\le r),\] where \(\|\mu-\pi\|_{\mathrm{TV}}\le \eta\). Hence \[d_{x^*}(m-1)\le \alpha\eta+(1-\alpha)\|\nu-\pi\|_{\mathrm{TV}} \le \eta+\mathbb{P}_{x^*}(\tau>r).\] But \(t_{\mathrm{mix}}(x^*)=m\), so \(d_{x^*}(m-1)>1/4\). With \(q:=1/4-\eta>0\), this yields \[\mathbb{P}_{x^*}(\tau>r)>q.\] On the other hand, Lemma 5.2 and Markov’s inequality give \[\mathbb{P}_{x^*}(\tau>r)\le \frac{\mathbb{E}_{x^*}\tau}{r}\le \frac{4\Delta s^2}{r}.\] For \(m\ge 4\), using \(r\ge m/4\), we obtain \[s\ge \sqrt{\frac{qr}{4\Delta}}\ge \sqrt{\frac{q}{16\Delta}}\sqrt m.\] Since \(C\subseteq B\), this proves the desired bound in the case \(C\subsetneq V\). Combining this with the case \(C=V\) and decreasing the constant to handle \(m<4\) completes the proof. ◻
Remark 7 (Sharpness and the bounded-degree hypothesis). The exponent \(1/2\) cannot be improved under only a bounded-degree assumption. For the path \(P_N\), lazy simple random walk has \(t_{\mathrm{mix}}(P_N)=\Theta(N^2)\), so the whole state space has size only \(\Theta(\sqrt{t_{\mathrm{mix}}(P_N)})\); see, for example, [9]. The bounded-degree assumption is also essential. A barbell or lollipop graph with clique size and connecting path length of order \(M\) has \(\Theta(M)\) vertices but mixing time \(\Theta(M^3)\), so no lower bound of order \(\sqrt{t_{\mathrm{mix}}}\) can hold without a degree bound.
Acknowledgment↩︎
The authors thank Russell Lyons for pointing out that the degree dependence in the return-probability estimate used in earlier drafts is necessary. They also thank Yuval Peres for sending the references [4], [5]. This work was partially supported by the ERC consolidator grant CUTOFF (101123174).