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.

  • $\begingroup$ A good resource on simple random walks in general is "Random Walk a Modern Introduction", by Lawler and Limic. It's available for free on Lawler's website: math.uchicago.edu/~lawler/srwbook.pdf $\endgroup$ – Jeremy Voltz Nov 15 '12 at 19:14

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.

  • $\begingroup$ Thank you for your answer! Apparently, I have not thought my question completely through, sorry for that. I think I am interested in the distribution of the time to reach a certain vertex. I'll adjust my question accordingly. $\endgroup$ – carnage Nov 15 '12 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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