Take the 2-minute tour ×

Please imagine a discrete random walk on an N-dimensional rectangular lattice with dimensional lengths $(l_1, ..., l_N) \in L$ and total lattice points $P = \prod{l_i}$, for $i = 1, ..., N$. At each time step, the walker will move to one of it's adjacent lattice points with equal probability. The N-dimensional random walk is non-self-avoiding, the walker must move with each time step, and the boundaries of the lattice are reflecting. However, jump probabilities must be adjusted at edges and corners due to a reduction in the number of adjacent nodes - i.e. jump probabilities will vary from $\frac{1}{2N}$ internal to the lattice to $\frac{1}{N}$ at the edges of the lattice.

Provided the random walk specifications above, what might be the expected step-time distribution for the walker visiting every position in the N-dimensional rectangular lattice with dimensional lengths $L$?

share|improve this question
@Rob: Under the interpretation that "adjaceny" means four neighbors in 2D, and "reflection" means that an attempt to step +1 out steps instead -1 in, and starting at the central point, then just empirically, for N=2 and L=3 (so a 3x3 array of lattice points), I find it takes about 40 steps to visit all 9 points. For L=5 (5x5 array), it takes about 218 steps to visit the 25 points. Very crude calculations, but might help in comparison to theoretical results... –  Joseph O'Rourke Aug 16 '10 at 18:01
It might be easier to solve the analogous problem for the N-dimensional torus, since you don't have to deal with boundary conditions. (I'm pretty sure I've seen a solution for the 1-torus, i. e. the circle, although I don't remember where I saw it or what the result is.) Depending on why you asked the question, this may or may not be helpful. –  Michael Lugo Aug 16 '10 at 19:19
Dear Joseph, yes, you interpreted my question pretty much right, but I'm handling the boundary conditions in a slightly different way. Instead of making a +1 step a -1 step, I reweigh the jump probabilities to account for an absence of a +1 node. Shouldn't making a +1 step into a -1 step overweigh the -1 node if N is larger than 1? –  Rob Grey Aug 17 '10 at 1:13
@Rob: Your exact reflection rule depends on your application; I just explored what was easiest to implement. –  Joseph O'Rourke Aug 17 '10 at 1:52
Joseph, apologies, that wasn't a criticism of your approach. I just wanted to clarify what I had in mind! –  Rob Grey Aug 17 '10 at 2:12

1 Answer 1

up vote 9 down vote accepted

If you look for "cover time of graph" you will find a lot of references, cf. e.g. "Jonasson, Schramm, ON THE COVER TIME OF PLANAR GRAPHS, Elect. Comm. in Probab. 5 (2000) 85-90, http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/include/getdocbfb7.pdf. In this paper you find the following result by Zuckermann (for details pls. cf the paper):

If $G$ is a finite portion of a $d$-dimensional lattice $\mathbb{Z}$ with $n$ vertices, the expected cover time (to visit all vertices) is $\Theta(n^2)$ for $d=1$, $\Theta(n (\log n)^2)$ for $d=2$, and $\Theta(n \log n)$ for $d \ge 3$.

share|improve this answer
Wow... that's exactly what I was looking for! –  Rob Grey Aug 17 '10 at 1:16

Your Answer


