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

  • $\begingroup$ @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... $\endgroup$ – Joseph O'Rourke Aug 16 '10 at 18:01
  • $\begingroup$ 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. $\endgroup$ – Michael Lugo Aug 16 '10 at 19:19
  • $\begingroup$ 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? $\endgroup$ – Rob Grey Aug 17 '10 at 1:13
  • 1
    $\begingroup$ @Rob: Your exact reflection rule depends on your application; I just explored what was easiest to implement. $\endgroup$ – Joseph O'Rourke Aug 17 '10 at 1:52
  • $\begingroup$ Joseph, apologies, that wasn't a criticism of your approach. I just wanted to clarify what I had in mind! $\endgroup$ – Rob Grey Aug 17 '10 at 2:12

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

  • $\begingroup$ Wow... that's exactly what I was looking for! $\endgroup$ – Rob Grey Aug 17 '10 at 1:16

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.