Timeline for Reference Request: Cover time for simple random walk on $n \times n$ torus
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2017 at 18:42 | comment | added | Yuval Peres | 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 | |
| Apr 18, 2012 at 0:49 | comment | added | Max | 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. | |
| Apr 18, 2012 at 0:40 | comment | added | Max | 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$. | |
| Apr 17, 2012 at 23:15 | vote | accept | David White | ||
| Apr 17, 2012 at 18:55 | comment | added | Henry Cohn | Even if you had used $O(n^4)$, better to be too pessimistic than to be wrong. | |
| Apr 17, 2012 at 18:41 | comment | added | David White | +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$ | |
| Apr 17, 2012 at 17:50 | history | answered | Max | CC BY-SA 3.0 |