Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 –  Gerhard Paseman Apr 17 '12 at 17:20

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
+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$ –  David White Apr 17 '12 at 18:41
    
Even if you had used $O(n^4)$, better to be too pessimistic than to be wrong. –  Henry Cohn Apr 17 '12 at 18:55
1  
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$. –  Max Apr 18 '12 at 0:40
2  
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. –  Max Apr 18 '12 at 0:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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