8
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\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
    Commented Aug 16, 2010 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
    Commented Aug 16, 2010 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
    Commented Aug 17, 2010 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
    Commented Aug 17, 2010 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
    Commented Aug 17, 2010 at 2:12

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow... that's exactly what I was looking for! $\endgroup$
    – Rob Grey
    Commented Aug 17, 2010 at 1:16

You must log in to answer this question.

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