13
$\begingroup$

I've been taken by the concise result1 that (roughly!), on a $2$-dimensional torus $\mathbb{T}^2$, the time it takes to visit nearly every point (within $\epsilon$, as $\epsilon \to 0$) is: $\frac{2}{\pi}$.

My question is:

Q. Is the same situation known for the $d$-dimensional torus, $\mathbb{T}^d$? What is the time it takes for a Brownian-motion particle to visit within $\epsilon \to 0$ of every point of $\mathbb{T}^d$?

This is probably known—or known to be unknown—so this is just a reference request.


1 Dembo, Amir, Yuval Peres, Jay Rosen, and Ofer Zeitouni. "Cover times for Brownian motion and random walks in two dimensions." Annals of Mathematics (2004): 433-464. Annals link.

$\endgroup$
  • 3
    $\begingroup$ Wouldn't it be more accurate to say that the time it takes is $2/ \pi \cdot |\log \epsilon|^2$? Not sure if I am misinterpreting the abstract of their paper. $\endgroup$ – Harry Richman Apr 24 at 23:55
  • $\begingroup$ @HarryRichman: What I see is $$\lim_{\epsilon\to0} \frac{C_\epsilon}{({\ln \epsilon})^2} = \frac{2}{\pi}$$ where $C_\epsilon$ is the time to come w/in $\epsilon$. $\endgroup$ – Joseph O'Rourke Apr 24 at 23:58
8
$\begingroup$

A very general answer, in dimension $d\geq 3$, is in the following paper of Dembo, Peres and Rosen https://projecteuclid.org/euclid.ejp/1464037588: for compact $d$-dimensional manifolds, $$C_\epsilon(M) /\epsilon^{2-d}\to V(M)$$ where $V(M)$ is the volume.

The $d$ dimensional case for $d\geq 3$ is much simpler than $d=2$ because in the latter, you have long range (=logarithmic) correlations arising from the recurrence of BM.

In passing, let me mention that Belius's paper mentioned in Josiah Park's answer gives a more refined answer, namely a limit law for a centered version of $\sqrt{C_\epsilon}$ (with no scaling), for the random walk case. Similar results can be written for the manifold case in $d\geq 3$. For the critical case of $d=2$, higher precision than the law of large numbers is available but as of this writing, the limit law for $\sqrt{C_\epsilon}-E\sqrt{C_\epsilon}$ has not been derived.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

It looks like the $d$-dimensional case is easier generally than the $d=2$ case according to the excerpt below from this paper (see page three).

...the two-dimensional model is also more difficult than its higher-dimensional counterparts. This is because dimension two is critical for the walk, resulting in strong correlations. To illustrate the dimension-based comparison, observe that very fine results are available for d ≥ 3, see e.g. 2 and references therein... In contrast, in two dimensions the first-order asymptotics of the cover time was completed only recently, after a series of intermediate steps over a decade of efforts.

Looking at Aldous and Fill's book (Corollary 7.24) there is an expression for the cover time for $(\mathbb{Z}/n\mathbb{Z})^d$ for $d\geq 3$, $T\sim R_d n \log n$, where

$$R_d=\int_{0}^1\dots\int_{0}^1\frac{1}{\frac{1}{d}\sum_{u=1}^d(1-\cos{2\pi x_u})}dx_1\dots dx_d.$$

In the limit as $n\rightarrow \infty$ with appropriate normalization, it appears this constant $R_d$ is the cover time.

2: D. Belius (2013) Gumbel fluctuations for cover times in the discrete torus. To appear in: Probab. Theory Relat. Fields. Prelininary arXiv abs.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.