on cover times for two-dimensional random walks

Overview

Dembo, Peres, Rosen, and Zeitouni prove the sharp cover-time constants for Brownian motion on compact two-dimensional manifolds and for simple random walk on the two-dimensional discrete torus (Dembo et al., 2004). If $M$ is a smooth, compact, connected Riemannian surface without boundary and area $A$, the time needed for Brownian motion to come within distance $\epsilon$ of every point is almost surely asymptotic to

$$\frac{2A}{\pi }{\left(\log \frac{1}{\epsilon }\right)}^2.$$

If $T_n$ is the cover time of the side-length $n$ torus ${\mathbb{Z}}_n^2$, then

$$\frac{T_n}{n^2(\log n{)}^2}⟶\frac{4}{\pi }$$

in probability. Combined with Aldous’s earlier concentration result $T_n/\mathbb{E}{T}_n\to 1$, this also identifies the expectation asymptotic.

The proof is a two-dimensional logarithmic-potential argument. On the unit torus, a fixed $\epsilon$-ball is missed up to Brownian time $y(\log (1/\epsilon ){)}^2$ with probability roughly ${\epsilon }^{\pi y}$, while there are roughly ${\epsilon }^{-2}$ possible balls to cover; the competition between these two exponents gives the threshold $y=2/\pi$. The lower bound is the hard part: the authors construct many candidate points with controlled multiscale excursion histories and use a second-moment argument to show that at least one small disk remains unvisited.

🏷️ Cover Time in Dimension Two

For a finite Markov chain, the cover time is

$$T_{\mathrm{cov}}=\inf \{t:\{X_0,X_1,\dots ,X_t\}=\Omega \}.$$

On the discrete torus

$${\mathbb{Z}}_n^2=(\mathbb{Z}/n\mathbb{Z}{)}^2,$$

there are $n^2$ sites, and the simple random walk moves to one of the four nearest neighbors at each step.

For Brownian motion $W_t$ on a compact Riemannian surface $M$, the pointwise cover time is not the right continuum notion: planar Brownian motion visits every small neighborhood of a point but does not hit every point of a two-dimensional continuum. The paper therefore studies the $\epsilon$-cover time

$${\mathcal{C}}_{\epsilon }=\inf \{t:M\subseteq {\cup }_{0\le s\le t}B(W_s,\epsilon )\}.$$

Equivalently,

$${\mathcal{C}}_{\epsilon }=\underset{x\in M}{\sup }{\tau }_x(\epsilon ),{\tau }_x(\epsilon )=\inf \{t:d(W_t,x)\le \epsilon \}.$$

Dimension two is the borderline case. The walk is recurrent, so every fixed lattice site is eventually hit, but the Green function has a logarithmic singularity. A single prescribed site in ${\mathbb{Z}}_n^2$ has a hitting time of order $n^2\log n$. A coupon-collector heuristic then suggests one extra factor $\log n$, hence $n^2(\log n{)}^2$. The theorem identifies the constant and proves that the strong correlations between nearby unvisited sites do not change it.

Two-Dimensional Cover-Time Constants

For Brownian motion on the unit flat torus ${\mathbb{T}}^2$,

$$\frac{{\mathcal{C}}_{\epsilon }}{(\log (1/\epsilon ){)}^2}⟶\frac{2}{\pi }$$

almost surely as $\epsilon \downarrow 0$.

More generally, let $M$ be a smooth, compact, connected, two-dimensional Riemannian manifold without boundary and area $A$. Then

$$\frac{{\mathcal{C}}_{\epsilon }}{(\log (1/\epsilon ){)}^2}⟶\frac{2A}{\pi }$$

almost surely as $\epsilon \downarrow 0$.

Let $T_n$ be the cover time of simple random walk on ${\mathbb{Z}}_n^2$. Then

$$\frac{T_n}{(n\log n{)}^2}⟶\frac{4}{\pi }$$

in probability as $n\to \infty$.

The paper’s numbering is discrete first: Theorem 1.1 is the random-walk result, Theorem 1.2 is Brownian motion on ${\mathbb{T}}^2$, and Theorem 1.3 is the general compact-surface extension. The constants are consistent under diffusive scaling. Scale the side-length $n$ torus down to the unit torus. A simple random walk of $k$ steps corresponds to Brownian time about $k/(2n^2)$, because one step has covariance $(1/2)I_2$ while standard planar Brownian motion has covariance $t{I}_2$. A Brownian $\epsilon$-cover with $\epsilon \approx 1/n$ therefore predicts

$$k\approx 2n^2\cdot \frac{2}{\pi }(\log n{)}^2=\frac{4}{\pi }{n}^2(\log n{)}^2.$$

🏷️ The Annulus Computation

The local calculation is the gambler’s-ruin estimate for planar Brownian motion in an annulus. Suppose

$$0<\epsilon <r<R$$

and Brownian motion starts at radius $r$ from a point $x$. Then the probability of hitting the inner circle $\partial B(x,\epsilon )$ before the outer circle $\partial B(x,R)$ is (by Kakutani’s Theorem)

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

This follows because $\log |z-x|$ is harmonic away from $x$ and has boundary values $\log \epsilon$ and $\log R$ on the two circles.

Choose $R$ small and $r=R/e$, as in the paper’s upper-bound proof. Then a path started on $\partial B(x,r)$ has only probability

$$\frac{1}{\log (R/\epsilon )}$$

of hitting $B(x,\epsilon )$ before returning to $\partial B(x,R)$.

The second local input is the duration of the excursions used by DPRZ. Their excursion starts at $\partial B(x,R)$, runs inward until it reaches $\partial B(x,r)$, and then returns to $\partial B(x,R)$. On the unit torus, uniformly for small $r<R$, the mean duration of one such outer-to-outer excursion is

$$\frac{1+o(1)}{\pi }\log \frac{R}{r}.$$

Moreover, sums of many such excursion durations concentrate around the corresponding multiple of this mean. The factor $1/\pi$ is the normalization of the two-dimensional Green function for Brownian motion with generator $\frac{1}{2}\Delta$.

Combining these two facts, Brownian time $y(\log (1/\epsilon ){)}^2$ corresponds to about

$$\pi y{\left(\log \frac{1}{\epsilon }\right)}^2$$

completed outer-to-outer excursions when $\log (R/r)=1$. During each completed excursion, the outward leg from $\partial B(x,r)$ to $\partial B(x,R)$ has the hitting probability above. The chance that all these excursions miss $B(x,\epsilon )$ is heuristically

$${\left(1-\frac{1}{\log (R/\epsilon )}\right)}^{\pi y\log (1/\epsilon {)}^2}\approx {\epsilon }^{\pi y}.$$

The paper turns this into the uniform upper-tail estimate: for every fixed $\delta >0$,

$$\mathbb{P}\{{\tau }_x(\epsilon )\ge y(\log \epsilon {)}^2\}\le C{\epsilon }^{(1-\delta )\pi y}$$

for all $x$, all starting points, all $y\ge 0$, and all small enough $\epsilon$. Since $(\log \epsilon {)}^2=(\log (1/\epsilon ){)}^2$, this is the estimate used below.

🏷️ Upper Bound

For the unit torus, the upper bound is a union bound after reducing the continuum to a controlled net. Take a maximal $\delta \epsilon$-separated set ${\mathcal{N}}_{\epsilon }$. It has

$$|{\mathcal{N}}_{\epsilon }|\asymp {\epsilon }^{-2}$$

points, and if every net point has been hit at radius comparable to $\epsilon$, then every point of the torus is covered at radius slightly larger than $\epsilon$.

For a fixed net point $x$, the tail estimate gives

$$\mathbb{P}\{{\tau }_x(\epsilon )>y(\log (1/\epsilon ){)}^2\}\lesssim {\epsilon }^{(1-\delta )\pi y}.$$

Therefore

$$\mathbb{P}\{\exists x\in {\mathcal{N}}_{\epsilon }:{\tau }_x(\epsilon )>y(\log (1/\epsilon ){)}^2\}\lesssim {\epsilon }^{-2+(1-\delta )\pi y}.$$

This tends to zero once

$$y>\frac{2}{\pi }.$$

The paper implements this on the deterministic sequence ${\epsilon }_n=e^{-n}$ and uses Borel-Cantelli plus monotonicity in $\epsilon$ to obtain the almost-sure bound

$$\underset{\epsilon \downarrow 0}{\mathrm{limsup}}\frac{{\mathcal{C}}_{\epsilon }}{(\log (1/\epsilon ){)}^2}\le \frac{2}{\pi }$$

on the unit torus. The area factor $A$ is recovered in the manifold extension.

Why the net argument is legitimate

A small disk around an arbitrary point is contained in a slightly larger disk around a nearby net point. The proof uses this geometric fact with nested radii, so the Brownian path need not literally hit the net point. It only has to enter a disk whose radius is chosen with enough slack to cover the nearby continuum points.

🏷️ Lower Bound and the Multiscale Second Moment

The lower bound cannot be obtained by a direct independence argument. If two points $x$ and $y$ are close, then the events

$$\{{\tau }_x(\epsilon )>t\},\{{\tau }_y(\epsilon )>t\}$$

are strongly correlated because Brownian excursions around $x$ and $y$ share their outer annuli. The proof resolves this by measuring how far down the sequence of nested annuli the path has penetrated.

Fix $a<2$. The paper first chooses a rapidly decreasing sequence

$${\epsilon }_k={\epsilon }_1(k!{)}^{-3}$$

and, for each large $n$, sets

$${\epsilon }_{n,k}={\rho }_n{\epsilon }_n(k!{)}^3,{\rho }_n=n^{-25},1\le k\le n.$$

This gives the nested family

$${\epsilon }_{n,1}<{\epsilon }_{n,2}<\cdots <{\epsilon }_{n,n}.$$

Around a candidate point $x$, let $N_{n,k}^x$ denote the number of excursions from radius ${\epsilon }_{n,k-1}$ to radius ${\epsilon }_{n,k}$ before a prescribed number of outermost excursions has occurred. The outer count is fixed at

$$N_{n,n}^x=n_n,n_k=3a{k}^2\log k.$$

The excursion counts behave like a branching process. One excursion at scale $k$ creates a random number of excursions at scale $k-1$ before the path escapes back outward. By the logarithmic gambler’s-ruin estimate, this offspring distribution is close to geometric with mean near one. Thus

$$N_{n,n}^x,N_{n,n-1}^x,\dots ,N_{n,2}^x$$

is approximately a critical Galton-Watson process run from the outside inward.

The authors call a point $n$-successful if the innermost relevant count is zero,

$$N_{n,2}^x=0,$$

and the intermediate counts stay in the narrow corridor

$$n_k-k\le N_{n,k}^x\le n_k+k,3\le k\le n-1.$$

If $x$ is $n$-successful, then the disk of radius ${\epsilon }_{n,1}$ around $x$ has not been hit by the time the outer excursions are completed.

For a single candidate point, Lemma 3.1 gives

$$\mathbb{P}\{x\text{ is }n\text{-successful}\}\ge {\epsilon }_n^{a+o(1)}.$$

Since the chosen square is partitioned into about ${\epsilon }_n^{-2}$ candidate centers, the expected number of successful points grows like

$${\epsilon }_n^{-2+a+o(1)},$$

which diverges for every $a<2$.

The main technical work is the pair estimate. If $x$ and $y$ separate at scale $\ell$, their excursion histories are essentially identical above $\ell$ and nearly independent below $\ell$. The corridor prevents the common outer history from producing too many descendants at the splitting scale. Summing over pairs at each possible separation scale gives a second-moment bound strong enough that the number $Z_n$ of successful points satisfies

$$\mathbb{P}\{Z_n=0\}\to 0$$

along a suitable deterministic subsequence; Borel-Cantelli upgrades this to the almost-sure lower bound.

Proof: From a Successful Point to the Lower Bound

If $x$ is successful, then the Brownian path has completed many excursions at large scales around $x$ but has not entered $B(x,{\epsilon }_{n,1})$. The total time of the outer excursions concentrates around its mean. With the paper’s choice

$$N_{n,n}^x=3a{n}^2\log n,$$

and with adjacent outer radii satisfying

$$\log \frac{{\epsilon }_{n,n}}{{\epsilon }_{n,n-1}}=3\log n,$$

the total time is

$$\left(\frac{a}{\pi }+o(1)\right){\left(\log \frac{1}{{\epsilon }_{n,1}}\right)}^2$$

on the unit torus. On a surface of area $A$, the same estimate is multiplied by $A$.

Therefore, with high probability, some ${\epsilon }_{n,1}$-ball is still unvisited at time

$$\left(\frac{aA}{\pi }-o(1)\right){\left(\log \frac{1}{{\epsilon }_{n,1}}\right)}^2.$$

Since $a<2$ was arbitrary, this yields

$$\underset{\epsilon \downarrow 0}{\mathrm{liminf}}\frac{{\mathcal{C}}_{\epsilon }}{(\log (1/\epsilon ){)}^2}\ge \frac{2A}{\pi }.$$

This is the conceptual heart of the paper. The lower bound is not just a reverse union bound; it is a controlled construction of late points whose correlation structure is handled by the tree-like geometry of annuli.

🏷️ From Brownian Motion to Random Walk

The paper deduces the random-walk lower bound from the Brownian theorem by a strong approximation. Fix $\gamma >0$ and set

$${\epsilon }_n=2n^{\gamma -1}.$$

The Brownian theorem implies that, with high probability, some disk of radius ${\epsilon }_n$ is still unvisited by Brownian motion on the unit torus up to time

$$\frac{2}{\pi }(1-\gamma -o(1){)}^2(\log n{)}^2.$$

A Komlos-Major-Tusnady type coupling, in Einmahl’s multidimensional form, constructs planar Brownian motion $W_t$ and simple random walk $S_k$ so that, after Brownian scaling and reduction modulo the unit torus,

$$\underset{k\le 4n^2(\log n{)}^2}{\max }\left|W_{k/(2n^2)}-\frac{S_k}{n}\right|\le \frac{{\epsilon }_n}{2}$$

with high probability. Hence if Brownian motion misses an ${\epsilon }_n$-disk, the rescaled walk misses a disk of radius ${\epsilon }_n/2=n^{\gamma -1}$; in lattice units the walk misses a disk of radius $n^{\gamma }$. Therefore it cannot have covered ${\mathbb{Z}}_n^2$. Multiplying Brownian time by $2n^2$ gives

$$\left(\frac{4}{\pi }-o(1)\right)(1-\gamma {)}^2{n}^2(\log n{)}^2.$$

Letting $\gamma \downarrow 0$ gives the random-walk lower bound. The matching upper bound is the known Aldous-Fill upper bound cited in the paper.

The factor of two

The Brownian constant on the unit torus is $2/\pi$, while the random-walk constant is $4/\pi$. This is not a contradiction. It comes from the diffusion normalization: standard planar Brownian motion has covariance matrix $t{I}_2$, while one step of the nearest-neighbor walk has covariance $(1/2)I_2$. One Brownian unit of time corresponds to about $2n^2$ random-walk steps after scaling space by $1/n$.

🏷️ General Compact Surfaces

The proof for a general smooth compact connected surface without boundary uses the same local annulus picture. First rescale the metric to reduce to area one. If the original metric is $g$ and the area is $A$, then replacing $g$ by $g/A$ produces an area-one surface, and Brownian time scales by $A$.

Locally, every smooth two-dimensional Riemannian metric is conformally Euclidean in isothermal coordinates. In such a coordinate patch, Brownian motion is a time change of planar Brownian motion. The time change affects how long an excursion takes, but not the logarithmic harmonic-measure computation that decides whether an excursion reaches the inner disk before escaping outward.

The mean duration of the relevant excursions is multiplied by $A$, while the one-excursion hit probability inside a small annulus is still governed by the logarithmic harmonic function. Therefore the unit-torus constant $2/\pi$ becomes

$$\frac{2A}{\pi }.$$

Curvature and coordinate errors are lower order because the proof uses radii that shrink to zero and keeps fixed slack between adjacent logarithmic scales.

🏷️ How Fast Does the Cover Time Converge?

There is a sharp answer at the next order, but it should be read as a second-order asymptotic rather than a practical finite-size error bound. The convergence is logarithmically slow.

For Brownian motion on the unit two-dimensional torus, Belius and Kistler proved the subleading correction (Belius & Kistler, 2017). If

$$L=\log \frac{1}{\epsilon },$$

then their result is

$$\frac{{\mathcal{C}}_{\epsilon }}{(1/\pi )L}=2L-(1+o(1))\log L$$

in probability. Equivalently,

$${\mathcal{C}}_{\epsilon }=\frac{2}{\pi }{L}^2-\frac{1}{\pi }L\log L+o(L\log L).$$

The negative correction means the true cover time is eventually a little smaller than the leading-order estimate $(2/\pi )L^2$.

For the discrete torus, Abe proved the corresponding second-order term (Abe, 2021). There is a constant $c\in (0,1)$ such that, with probability tending to one,

$$2\log n-\log \log n-(\log \log n{)}^c\le \frac{T_n}{(2/\pi )n^2\log n}\le 2\log n-\log \log n+(\log \log n{)}^c.$$

Multiplying out gives

$$T_n=\frac{4}{\pi }{n}^2(\log n{)}^2-\frac{2}{\pi }{n}^2\log n\log \log n+O_{\mathbb{P}}(n^2\log n(\log \log n{)}^c),$$

or, in the normalization used by DPRZ,

$$\frac{T_n}{n^2(\log n{)}^2}=\frac{4}{\pi }-\frac{2}{\pi }\frac{\log \log n}{\log n}+O_{\mathbb{P}}\left(\frac{(\log \log n{)}^c}{\log n}\right).$$

Thus the natural scale of convergence is not a power of $n$; the first visible correction is of order

$$\frac{\log \log n}{\log n}.$$

This is very slow. At $n=96$, for example, $\log \log n/\log n=0.333$ to three decimals, so the formal second-order correction is still about $0.212$ in the normalized units.

What this rate does and does not say

The second-order theorem locates the asymptotic center up to a window of order $(\log \log n{)}^c/\log n$ after normalization. It does not give a small-$n$ confidence interval, and the exponent $c$ is not meant as a numerically optimized finite-size bound. The correction eventually has negative sign, but modest simulations can still sit above $4/\pi$ because higher-order terms and lattice effects dominate until very large $n$.

📊 Numerical Verification

The script content/codes/2026 Summer/cover_times_2d_torus.py simulates simple random walk on ${\mathbb{Z}}_n^2$ and reports the normalized cover time

$$\frac{T_n}{n^2(\log n{)}^2}.$$

The default run uses independent walks at modest sizes and writes the plot below. The dashed horizontal line is the DPRZ limit $4/\pi$, while the dotted line is the center predicted by Abe’s second-order term,

$$R_2(n)=\frac{4}{\pi }-\frac{2}{\pi }\frac{\log \log n}{\log n}.$$

side length $n$	trials	mean $T_n/(n^2(\log n{)}^2)$	s.e.	2nd-order center	mean - center	median
16	256	1.4933	0.0226	1.0391	0.4542	1.4442
24	192	1.4250	0.0218	1.0416	0.3834	1.3623
32	160	1.4159	0.0217	1.0449	0.3710	1.3733
48	96	1.3848	0.0265	1.0506	0.3341	1.3616
64	64	1.3557	0.0311	1.0551	0.3006	1.3403
96	32	1.3024	0.0356	1.0615	0.2409	1.2574

The leading target constant is

$$\frac{4}{\pi }=1.2732395447\dots .$$

The simulated means drift downward toward this value; at $n=96$ the difference from $4/\pi$ is about $0.029$, smaller than one reported standard error. This is a reasonable sanity check of the leading DPRZ constant, not a precision estimate.

The second-order comparison is more instructive as a warning about scale. The formal center $R_2(n)$ is below $4/\pi$ already for these $n$, while the simulated means are still above $4/\pi$. This does not contradict Abe’s theorem: after normalization, the unshown error window is of order $(\log \log n{)}^c/\log n$, and $\log \log n/\log n$ is still about $0.333$ at $n=96$. Numerically, the visible effect is only that the gap between the Monte Carlo mean and the second-order center decreases from $0.454$ at $n=16$ to $0.241$ at $n=96$.

See Also

• on Dudley’s Theorem: Both topics use multiscale decompositions; Dudley’s theorem chains Gaussian increments, while the cover-time proof chains annular excursions.
• on Slepian’s lemma and Gaussian comparison: Useful background for comparison methods in Gaussian processes, which are conceptually close to the late-point heuristics for two-dimensional fields.
• on random matrices and complexity of spin glasses: Another example where a first-moment estimate is insufficient and the main work is controlling correlations through a second-moment argument.
• on second moments and extremal critical points of p-spin glasses: The successful-point construction is structurally similar to extremal-process proofs where rare candidates must be separated by their overlap or common history.

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. & 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.