on high-dimensional cover times and random interlacements

Overview

In two dimensions, the cover time of the discrete torus is of order $N^2(\log N{)}^2$ because the Green function itself grows like $\log N$ (Dembo et al., 2004). In dimensions $d\ge 3$, the random walk is transient at the local scale, and the discrete-torus cover time is instead

$$g(0)N^d\log (N^d)$$

up to the usual continuous/discrete-time convention (Belius, 2013). The right replacement for the two-dimensional annulus calculation is not a product of logarithmic annuli. It is capacity, random interlacements, and approximate independence of well-separated late points.

This note is a companion to on cover times for two-dimensional random walks. The goal is to organize the literature clusters around one question: what replaces the two-dimensional Green-function annulus argument when $d\ge 3$?

The Dimension Split

For planar Brownian motion or two-dimensional random walk, the harmonic function in an annulus is logarithmic. If $\epsilon <r<R$, the model computation is

$${\mathbb{P}}_r({\tau }_{\epsilon }<{\tau }_R)=\frac{\log (R/r)}{\log (R/\epsilon )}.$$

This logarithmic interpolation is the source of the multiscale excursion tree in the two-dimensional proof. Each scale contributes a comparable amount, so the last points are governed by a log-correlated field and critical branching-type traversal counts.

In dimension $d\ge 3$, the corresponding annulus probability is Newtonian:

$${\mathbb{P}}_r({\tau }_{\epsilon }<{\tau }_R)=\frac{r^{2-d}-R^{2-d}}{{\epsilon }^{2-d}-R^{2-d}}.$$

The small target is seen through its capacity. If $R$ and $r$ are macroscopic compared with $\epsilon$, then the probability is of order $(\epsilon /r{)}^{d-2}$, not $1/\log (R/\epsilon )$. This is the first technical break with dimension two.

On ${\mathbb{Z}}^d$, $d\ge 3$, the Green function is finite:

$$g(0)=\sum _{n\ge 0}{\mathbb{P}}_0(X_n=0)<\infty .$$

Equivalently, a single point has capacity

$$\mathrm{cap}(\{0\})=\frac{1}{g(0)}.$$

For the walk on ${\mathbb{Z}}_N^d$, this gives the one-point late estimate

$$\mathbb{P}\{x\notin X[0,u{N}^d]\}\approx \exp \{-u/g(0)\}.$$

Thus at

$$u=g(0)(\log (N^d)+z),$$

the expected number of unvisited sites is close to $e^{-z}$, which is exactly the extreme-value scaling behind the high-dimensional Gumbel theorem.

Random Interlacements

The clean local model in dimensions $d\ge 3$ is Sznitman’s random interlacement process (Sznitman, 2010). It is a Poisson cloud of doubly infinite transient trajectories on ${\mathbb{Z}}^d$, modulo time shift. Its vacant set ${\mathcal{V}}^u$ is characterized by the capacity identity

$$\mathbb{P}[K\subset {\mathcal{V}}^u]=\exp \{-u\mathrm{cap}(K)\}$$

for every finite $K\subset {\mathbb{Z}}^d$.

This formula is the high-dimensional replacement for the annulus Green-function computation. The input is no longer a logarithmic crossing probability across each annulus. It is the equilibrium measure of the target, summarized by capacity.

Windisch proved the torus-to-interlacement local limit (Windisch, 2008). If $x_1,\dots ,x_M\in {\mathbb{Z}}_N^d$ are mutually far apart, then the local vacant pictures around these points at time $u{N}^d$ converge jointly to independent random-interlacement vacant sets at level $u$. The proof reduces the probability of avoiding a finite union

$$B=\bigcup _{i=1}^M(x_i+K_i)$$

to an exponential hitting-time estimate and the asymptotic identity

$$\frac{N^d}{\mathbb{E}[H_B]}⟶\sum _{i=1}^M\mathrm{cap}(K_i).$$

The latter is proved by comparing Dirichlet and Thomson principles on the torus with their infinite-lattice counterparts.

Gumbel Covering

Belius proved the sharp high-dimensional discrete-torus fluctuation theorem (Belius, 2013). For continuous-time simple random walk on ${\mathbb{Z}}_N^d$, $d\ge 3$, if $C_N$ is the cover time, then

$$\frac{C_N}{g(0)N^d}-\log (N^d)\Rightarrow G,$$

where $G$ is the standard Gumbel random variable.

The theorem is stronger for arbitrary large target sets $F\subset {\mathbb{Z}}_N^d$. With

$$u_F(z)=g(0)(\log |F|+z),$$

Belius proves a uniform estimate of the form

$$\underset{z}{\sup }\left|\mathbb{P}(C_F\le N^d{u}_F(z))-\exp (-e^{-z})\right|\le c|F{|}^{-c}.$$

The proof has three structural steps.

1. A random-interlacement coupling is built in many well-separated mesoscopic boxes. The walk trace in each box is squeezed between interlacements at levels $u(1-\delta )$ and $u(1+\delta )$.

2. After running the walk until slightly before the cover time, the late set

$$F_{\rho }=F\setminus X[0,N^d(1-\rho )g(0)\log |F|]$$

has size close to $|F{|}^{\rho }$ and is well separated with high probability.

3. Once the late set is sparse and separated, the remaining hitting times behave like almost independent exponentials. The maximum of these exponentials gives the Gumbel law.

This also describes the geometry of the very last sites. The point process of last vertices converges to a Poisson point process on the continuum torus with intensity $e^{-z}dx$, and the last fixed number of sites are macroscopically separated. That is the opposite of the two-dimensional picture, where late points retain a log-correlated multiscale geometry.

Late-Point Phase Transition

The Gumbel theorem studies the very end of covering. Prévost, Rodriguez, and Sousi study the broader late-point process before the final coupon-collector window (Prévost, Rodriguez & Sousi, 2026). Set

$$u_N(\alpha )=\alpha g(0)\log (N^d)$$

and let

$${\mathcal{L}}^{\alpha }={\mathbb{Z}}_N^d\setminus X[0,u_N(\alpha )N^d]$$

be the late set. Then

$$\mathbb{P}(0\in {\mathcal{L}}^{\alpha })\approx N^{-\alpha d}.$$

A Bernoulli approximation is true only above a threshold. If $D^{\alpha }$ counts nearest-neighbor pairs in the late set, then

$${\alpha }_{\ast }=\sup \{\alpha >0:\mathbb{E}{D}^{\alpha }\to 0\}=\frac{1}{2}\left(1+{\mathbb{P}}_0({\tilde{H}}_0<\infty )\right)\in (1/2,1).$$

Let ${\mathcal{B}}^{\beta }$ denote a monotone i.i.d. Bernoulli field with density $\mathbb{P}(0\in {\mathcal{L}}^{\beta })\sim N^{-\beta d}$. For $\alpha >{\alpha }_{\ast }$ and small $\epsilon >0$, one can couple

$${\mathcal{B}}^{\alpha +\epsilon }\subset {\mathcal{L}}^{\alpha }\subset {\mathcal{B}}^{\alpha -\epsilon }$$

with probability tending to one. At $\alpha ={\alpha }_{\ast }$ the optimal coupling probability tends to $e^{-d}$, and for $\alpha <{\alpha }_{\ast }$ no such sprinkled Bernoulli sandwich succeeds. The obstruction is the birth of neighboring late-point pairs.

The same paper gives a finite-pattern description. For a finite set $K$, define

$${\alpha }_{\ast }(K)=\frac{1}{g(0)\mathrm{cap}(K)}.$$

A translated copy of $K$ is expected to disappear once $\alpha$ passes ${\alpha }_{\ast }(K)$. The nearest-neighbor pair has threshold ${\alpha }_{\ast }$, but more distant two-point sets have thresholds descending toward $1/2$. For each fixed $\alpha >1/2$, the late set decomposes into bounded islands far apart, and these islands can be approximated by independent samples of admissible patterns. In dimensions $d\ge 4$, the admissible patterns are singletons and two-point sets. In dimension $d=3$, one must also include the two connected three-point shapes

$$K_1=\{(0,0),(0,1),(0,2)\},K_2=\{(0,0),(0,1),(1,0)\},$$

up to lattice symmetries. The proof uses localized local times, inverse soft local times, and a modified Chen-Stein argument to make the dependence finite range up to controlled errors.

This cluster explains how far the independence heuristic goes. The final few sites are asymptotically separated and Poissonian, but earlier late sets still remember the capacities of small connected patterns.

Brownian Porous Media

For Brownian motion on the continuum torus ${\mathbb{T}}^d$, $d\ge 3$, the relevant small object is an $\epsilon$-ball, whose Newtonian capacity is proportional to ${\epsilon }^{d-2}$. Goodman and den Hollander study the geometry of the complement of the Brownian path thickened by a small ball, a Brownian porous medium (Goodman & den Hollander, 2014).

Their natural scales are

$${\phi }_d(t)={\left(\frac{d\log t}{(d-2){\kappa }_{d}t}\right)}^{1/(d-2)}$$

for the largest holes at time $t$, and

$${\psi }_d(\epsilon )=\frac{{\epsilon }^{-(d-2)}\log (1/\epsilon )}{{\kappa }_d}$$

for the $\epsilon$-cover time. Here ${\kappa }_d$ is the Newtonian capacity of the unit ball in their normalization.

The associated cover-time large-deviation rate function is $I_d^{\mathrm{cover}}(u)=u-d$ for $u\ge d$ and $I_d^{\mathrm{cover}}(u)=\infty$ for $0<u<d$. In particular,

$$\frac{C_{\epsilon }}{{\psi }_d(\epsilon )}\to d$$

in probability. Equivalently, the leading scale is

$$\frac{d}{{\kappa }_d}{\epsilon }^{-(d-2)}\log (1/\epsilon ).$$

This is the continuum analogue of the capacity-coupon-collector principle: the number of potential holes contributes the logarithm, while the cost of hitting a small ball is governed by capacity.

The porous-medium results also give large-deviation information for the largest components of the vacant region. The qualitative lesson is useful for comparing with two dimensions. In $d\ge 3$, the dominant strategy for creating a late hole is spatial avoidance of a small-capacity set. In $d=2$, the obstruction is temporal and hierarchical: the walk repeatedly returns across logarithmic annuli, producing much stronger correlations.

General Graph Viewpoint

Ding, Lee, and Peres give a graph-universal comparison between cover times, blanket times, and Gaussian free fields (Ding, Lee & Peres, 2012). For a finite connected graph $G=(V,E)$ and a pinned Gaussian free field $({\eta }_v{)}_{v\in V}$,

$$t_{\mathrm{cov}}(G)\asymp |E|{\left(\mathbb{E}\underset{v\in V}{\max }{\eta }_v\right)}^2.$$

Equivalently, the cover time is controlled up to universal constants by Talagrand’s ${\gamma }_2$ functional for the metric $\sqrt{R_{\mathrm{eff}}}$.

This theorem is not designed to recover the exact constants in the torus results. Its value here is conceptual. On ${\mathbb{Z}}_N^d$, $d\ge 3$, the GFF maximum is of order $\sqrt{\log (N^d)}$ because the variance stays bounded, giving the scale $N^d\log (N^d)$. In two dimensions, the GFF variance grows like $\log N$, and the maximum is of order $\log N$, giving $N^2(\log N{)}^2$. The same dichotomy appears again, now through effective resistance and Gaussian comparison.

How the Clusters Fit

• $d=2$ discrete torus: the Green function grows like $\log N$, annuli are logarithmic, the cover scale is $N^2(\log N{)}^2$, and the late geometry is a log-correlated traversal tree.
• $d\ge 3$ discrete torus: the Green function is finite, point capacity is $1/g(0)$, the cover scale is $g(0)N^d\log (N^d)$, and the last sites are Gumbel, Poissonian, and separated.
• $d\ge 3$ late sets: finite-pattern capacities control visibility, the density at level $\alpha$ is $N^{-\alpha d}$, and pure Bernoulli behavior holds only above the nearest-neighbor threshold ${\alpha }_{\ast }$.
• $d\ge 3$ Brownian torus: ball capacity is ${\kappa }_d{\epsilon }^{d-2}$, the cover scale is $\frac{d}{{\kappa }_d}{\epsilon }^{-(d-2)}\log (1/\epsilon )$, and holes are governed by porous-medium large deviations.
• Finite graphs: effective resistance and the GFF control the cover time through $|E|(\mathbb{E}\max \eta {)}^2$ up to constants, with generic chaining as the organizing geometry.

The annulus remains useful in high dimensions, but its role changes. It is mainly a separation and decoupling device: one builds mesoscopic boxes, compares the walk trace in them to interlacements, and uses capacity to quantify what is avoided. In two dimensions, by contrast, annuli are the main scale-by-scale dynamical object; their logarithmic harmonic measure produces the critical branching structure that drives the second-order corrections of Belius-Kistler and Abe (Belius & Kistler, 2017; Abe, 2021).

See Also

• on cover times for two-dimensional random walks: the planar annulus and excursion-count proof behind the $N^2(\log N{)}^2$ law.
• on Slepian’s lemma and Gaussian comparison: comparison principles behind the GFF viewpoint.
• on Dudley’s Theorem: the chaining side of the Ding-Lee-Peres theorem.
• on second moments and extremal critical points of p-spin glasses: a parallel use of overlap geometry and second moments for extremes.

References

🐻  Abe, Y. 2021. Second-Order Term of Cover Time for Planar Simple Random Walk. Journal of Theoretical Probability 34(3), 1689–1747.

🐻  Belius, D. 2013. Gumbel Fluctuations for Cover Times in the Discrete Torus. Probability Theory and Related Fields 157(3–4), 635–689.

🐻  Belius, D. & Kistler, N. 2017. The Subleading Order of Two Dimensional Cover Times. Probability Theory and Related Fields 167(1–2), 461–552.

🐻  Dembo, A., Peres, Y., Rosen, J. & Zeitouni, O. 2004. Cover Times for Brownian Motion and Random Walks in Two Dimensions. Annals of Mathematics 160(2), 433–464.

🐻  Ding, J., Lee, J.R. & Peres, Y. 2012. Cover Times, Blanket Times, and Majorizing Measures. Annals of Mathematics 175(3), 1409–1471.

🐻  Goodman, J. & den Hollander, F. 2014. Extremal Geometry of a Brownian Porous Medium. Probability Theory and Related Fields 160(1–2), 127–174.

🐻  Prévost, A., Rodriguez, P.-F. & Sousi, P. 2026. Phase Transition for the Late Points of Random Walk. Probability Theory and Related Fields, 1–86.

🐻  Sznitman, A.-S. 2010. Vacant Set of Random Interlacements and Percolation. Annals of Mathematics 171(3), 2039–2087.

🐻  Windisch, D. 2008. Random Walk on a Discrete Torus and Random Interlacements. Electronic Communications in Probability 13, 140–150.