Thursday, 24 January 2008

co.combinatorics - Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice

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

No comments:

Post a Comment