Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability $1/4$. I want to know the distribution of the time that it takes to hit a certain vertex $(x,y)$. I have already done quite some research on related work but so far I was not able to come up with a paper that gives an answer to my question. I would appreciate any hint towards a paper that covers this problem or a hint on how I can calculate it myself.
[Math] Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid
markov chainspr.probabilityrandom walks
Related Solutions
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$.
Let $A_n$ be the adjacency matrix of the directed $n$-cycle without loops. That is for instance
$$A_4=\begin{bmatrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 1& 0 & 0 &0 \end{bmatrix}.$$ The transition matrix $P_n$ of your random walk is then given by $P_n=\frac{1}{2}A_n+\frac{1}{2}I_n$ where $I_n$ is the unit matrix. Let $\lambda(P_n)$ denote the second largest eigenvalue modulus of $P_n$, then the rate of convergence to the stationary distribution is for any starting vertex $i\in[n]$ (this is true for the undirected case and it should be true for the directed case as well):
$$\|P_n^t\cdot e_i-\left(\frac{1}{n},\dots,\frac{1}{n}\right)^T\|_2\le\lambda(P_n)^t.$$
(you are interessted in $\|\cdot\|_\infty$, but this can clearly be bounded from above in terms of $\|\cdot\|_2$). The eigenvalues of $P_n$ have precisely the form $\frac{1}{2}\mu+\frac{1}{2}$, where $\mu$ is an eigenvalue of $A_n$. The eigenvalues of $A_n$ are the unit roots, i.e. $\mu=\exp(\frac{2\pi ij}{n})$ for $j\in[n]$. Left to do is to figure out what
$$\lambda(P_n)=\max\left\{|\frac{1}{2}\exp(\frac{2\pi i j}{n})+\frac{1}{2}|: j\in[n-1]\right\}$$
is. Does that help?
Best Answer
Oops, too long for a comment:
The expectation of the time until you reach a given point other than the origin is infinite already in one dimension. To see this, let $T$ be the expected time until you get from 0 to 1 (in the obvious 1-dimensional setting). The first step is either to the left or to the right, and if you go to $-1$, the expected remaining time is going to be $2T$ since you have to get back to the origin and then to 1. Consequently $T = 1 + 1/2\cdot (2T)$, from which we see that finite $T$ leads to contradiction. In higher dimensions it becomes even worse. Presumably you want to modify your question and ask about something like the distribution of the time (in dimensions 1 and 2 you actually get there!) or about the expected time to get from one point to another in a finite box.