3
$\begingroup$

I'm putting the finishing touches on my masters thesis and need a reference for the following fact (which my advisor told me):

Let $G$ be the $n\times n$ grid and identify the sides to make it a torus. A simple random walk on $G$ is expected to take $O(n^4)$ time before it hits every vertex.

I've been googling for this all day with no luck. Does anyone know where I can find a statement of this result? I don't need the original reference...a textbook would be fine. Also, if you have a reference for $G$ being the $n\times n$ grid without sides identified I can make that work too. I just need this fact for the "previous work" section of the thesis...none of my results depend on it.

I read several things in [Lovasz's Survey][1] of Random Walks which gave upper bounds of $O(|V|^2)$ for various graphs, but none seem to apply to the grid case.

[1] http://www.cs.unibo.it/babaoglu/courses/cas/resources/tutorials/RandomWalks.pdf

Improve this question
$\endgroup$
1
  • $\begingroup$ You might be able to capitalize on the return time for an infinite grid. If it is O(n^2), then a return to the origin from a given direction is also O(n^2), and now you can traverse the grid in V^2*O(n^2) steps. Gerhard "Ask Me About System Design" Paseman, 2012.04.17 $\endgroup$
    – Gerhard Paseman
    Commented Apr 17, 2012 at 17:20

2 Answers 2

Reset to default
6
$\begingroup$

Markov Chains and Mixing Times by Levin, Peres and Wilmer. Section 11.3.2.

http://research.microsoft.com/en-us/um/people/peres/markovmixing.pdf

The expected cover time is of order $n^2(\log n)^2$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ +1: Thanks for the speedy answer. I'm doubly glad because having the reference saves me from saying "it is well-known that...$O(n^4)$" which would have been wrong. Do you happen to know of a reference for an $n\times n$ grid which is not a torus? Perhaps that's what my advisor was thinking of, though I can't imagine it would jump from $n^2\log^2(n)$ to $n^4$ $\endgroup$
    – David White
    Commented Apr 17, 2012 at 18:41
  • $\begingroup$ Even if you had used $O(n^4)$, better to be too pessimistic than to be wrong. $\endgroup$
    – Henry Cohn
    Commented Apr 17, 2012 at 18:55
  • 2
    $\begingroup$ Actually, if you look at the notes on p. 152, for your original problem, the expected cover time $E(\tau_{cov}) \sim \frac4\pi n^2(\log n)^2$. $\endgroup$
    – Max
    Commented Apr 18, 2012 at 0:40
  • 2
    $\begingroup$ For the case of $n\times n$ grid, I don't know the exact rate but I can provide an upper bound on the cover time. By the same Matthews method (Theorem 11.2 of the reference), the cover time is bounded from above by the (largest) hitting time multiplied by $2\log n$. The largest hitting time in this case is of order $n^2\log n$, which can be calculated through effective resistance and commute time identity (Propositions 9.16 and 10.6). Therefore, the cover time in the grid case can be bounded by $O(n^2(\log n)^2)$ too. $\endgroup$
    – Max
    Commented Apr 18, 2012 at 0:49
  • $\begingroup$ The asymptotic cover time result in [1] works for the grid as well as the torus.[1] Cover Times for Brownian Motion and Random Walks in Two Dimensions Amir Dembo, Yuval Peres, Jay Rosen and Ofer Zeitouni Annals of Mathematics Second Series, Vol. 160, No. 2 (Sep., 2004), pp. 433-464 $\endgroup$
    – Yuval Peres
    Commented Jan 19, 2017 at 18:42
1
$\begingroup$

The asymptotic cover time result in [1] (see comment 2 above) works for the grid as well as the torus. See comment 2 on page 28 in https://arxiv.org/pdf/math/0107191.pdf . Further refinements are in refs [2] and [3] below. In particular [2] considers the cover time of the 2d grid with a wired boundary. The boundary conditions do not affect the first order asymptotics.
[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)Vol. 160, No. 2 pp. 433-464.

[2] Ding, Jian. "On cover times for 2D lattices." Electron. J. Probab 17, no. 45 (2012): 1-18.

[3] Belius, David, and Nicola Kistler. "The subleading order of two dimensional cover times." Probability Theory and Related Fields (2014): 1-92.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .