Pólya showed that a random walk (with the directions at each step uniformly distributed) on the integer lattice returns with probability 1.

What if instead we consider the random walk where we are not allowed to go backwards? That is we start at (0,0) and facing "north", at each step we either turn left, stay straight, or turn right each with Pr = 1/3. For example the possible positions after 1 step are:

(-1,0) (facing west)

(0,1) (facing north)

(1,0) (facing east)

The distribution on the next step depends on the last step you took, so you cannot immediately return to the spot you just came from (this is what my friend does when he "randomly" walks in Manhattan, it is boring to turn completely around). Thus one possible return sequence would be 4 consecutive left turns.

Does this return with probability 1?

  • $\begingroup$ This amounts to introducing a drift term in your equation, so you will not return. But I would think that is evident. The moment you set a step north, you can not go back anymore. $\endgroup$ – Raskolnikov Dec 25 '11 at 21:11
  • $\begingroup$ Perhaps, I should be more precise. If your first two steps are left turns, then you will be at (-1,-1) and facing south. Thus if you make 4 consecutive left turns, you will be back at (0,0). $\endgroup$ – Justin Gilmer Dec 25 '11 at 21:15
  • 2
    $\begingroup$ So, the transition distribution changes as a function of the last step you took? Am I understanding that correctly? For example, conditional on step $\xi_n = (-1,0)$, the distribution of the next step $\xi_{n+1}$ is distributed uniform on $\{(-1,0), (0,-1), (0,1)\}$. $\endgroup$ – cardinal Dec 25 '11 at 21:19
  • $\begingroup$ @Justin: OK, I guessI didn't read your post carefully enough. $\endgroup$ – Raskolnikov Dec 25 '11 at 21:32
  • $\begingroup$ You might be interested in Jim Propp's rotor-router model(s), if you are not familiar with them. (They're not the same thing, though.) $\endgroup$ – cardinal Dec 25 '11 at 21:33

This is an example of a persistent random walk (these are also called Newton's random walks). Its recurrence is a consequence of a general theorem due to Jean-Pierre Conze on the recurrence of so-called dynamical cocycles.

For an introduction to persistent random walks and a sketch of the application of Conze's result to the specific case you asked about, see Theorem 2.5 of this paper and the references therein.

  • $\begingroup$ Thank you! I would mark this as answered, but not sure how. $\endgroup$ – Justin Gilmer Dec 26 '11 at 23:54
  • 2
    $\begingroup$ Looks like you found how to... Nice question, by the way. $\endgroup$ – Did Dec 27 '11 at 0:00

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.