Hitting times for an N-dimensional random walk on a lattice with (strictly positive) random integer steps

Question

Please consider a random walk on a finite N-dimensional lattice with vectors $(x_1, ..., x_N)$. We define the origin to be $(0, ..., 0)$ and the target to be at the point in the lattice furthest away from the origin - i.e. $(||x_1||, ..., ||x_N||)$ where $||x_k||$ is the integer length of the lattice in the $x_{k}$ dimension. Here, each step of the random walk is a uniformly distributed, strictly positive random integer in each of the N-dimensions with an upper-bound value defined by the requirement that one cannot exceed the dimensions of the lattice.

Is there a nice method, aside from explicit path-counting, to derive the probability density for hitting times provided an arbitrary lattice as defined above?

Some computational results: For the $N=1$ case I expected the target hitting time (defined as the number of steps to reach the target) to fit well with a logarithmic growth function of the form $A*ln(S)$ where A is a positive real number and $"S"$ is the number of integer steps one takes to reach the target from the origin. Running simulations (averaging 10,000 times) this yielded a decent fit with the value of $A$ ~ 1.146 for $||x|| = 100$, but $A$ decreases to ~1.095 for $||x|| = 1,000$ and decreased further ~1.069 for $||x||=10,000$.

Answer 1

Assuming you mean Leonid Kovalev's interpretation, the distribution of the hitting time in the $N = 1$ case is the same as the distribution of the number of cycles of a random permutation of $[n]$.

To be more specific, I'll change coordinates. Let $X_0 = (x_0^1, \ldots, x_0^N) = (S, S, \ldots, S)$. Let $X_1 = (x_1^1, \ldots, x_1^N)$, where $x_1^j$ is chosen uniformly at random from $0, 1, \ldots, x_0^j-1$. Define $X_2$ similarly in terms of $X_1$, and so on.

Then the sequence $(x_0^1, x_1^1, x_2^1, x_3^1, \ldots)$ are as follows:

• $x_0^1 = L$, of course.
• $x_1^1$ is uniformly distributed on $\{ 0, \ldots, S-1 \}$.
• $x_2^1$ is uniformly distributed on $\{ 0, \ldots, x_1^1-1 \}$.

and so on... In particular the distribution of $x_1^1$ is the distribution of number of elements in a random permutation on $S$ elements which are {\it not} in the cycle containing 1; In particular the distribution of $x_1^1$ is the distribution of number of elements in a random permutation on $S$ elements which are {\it not} in any of the $k$ cycles with the smallest minima.

So the distribution of the smallest $k$ for which $x_k^1 = 0$ is exactly the distribution of the number of cycles of a random permutation of $\{ 1, \ldots, S \}$; this is $1 + 1/2 + \cdots + 1/S \sim \log S + \gamma$, where $\gamma = 0.577\ldots$ is the Euler-Mascheroni constant.

In the higher-dimensional cases, the time to reach $(0, \ldots, 0)$ is just the {\it maximum} of the number of cycles of $N$ permutations chosen uniformly at random; this should still have expectation $\log S$ plus a constant depending on $N$.

Answer 2

While I like Michael Lugo's answer better, I thought I might as well put up the solution I sketched out for myself for the one-dimensional case:

The probability that the walker visits a particular point on the one-dimensional lattice can be expressed as $\frac{1}{||x_k||-p}$ where $p$ is the distance between the lattice point and the origin. Therefore, we can express the probability that, during a given step, the walker visits the target lattice point (i.e. the lattice point furthest from the origin) as - $P(target)$ = $\frac{(\frac{1}{||x_k||-(||x_k||-1)})}{\sum_{i=0}^{\||x_k||-1}\frac{1}{||x_k||-i}}$. $\frac{1}{P(target)}$ should therefore provide the average hitting time for the one-dimensional walkers under the imposed conditions. Computationally this value approximates Michael Lugo's answer of $ln(||x_k||)+\gamma$ within ~0.1 by $||x_k||$ = 5.