Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
This sounds a lot like directed percolation. ;) –  Gjergji Zaimi Feb 13 '10 at 3:08
    
How are you choosing your random step sizes? –  Qiaochu Yuan Feb 13 '10 at 3:08
    
Leonid, yes, that's exactly what I mean. One would generate a uniformly distributed random integer between '1' and the largest integer value that won't take you out of the lattice for each of the 'N' dimensions. –  Rob Grey Feb 13 '10 at 3:24
    
Leonid, I apologize, I misspoke. The overall step size must be non-zero, but movement in any subset of the dimensions may be zero for a step. I.e. one of the randomly generated integers must be at least one, but the remainder may be zero-valued. –  Rob Grey Feb 13 '10 at 3:35

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks for your answer Michael. –  Rob Grey Feb 13 '10 at 3:39
    
You're welcome! It just happens that I spend way too much time thinking about random permutations. That being said, the original problem was a little underspecified, and I happened to make the interpretations that led to me being able to solve it. In your second comment I see you actually had a different interpretation in mind. I suspect the overall behavior is the same -- still logarithmic -- but it would be harder to prove because the $N$ dimensions are no longer independent. –  Michael Lugo Feb 13 '10 at 3:50

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.