12
$\begingroup$

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?

  • 0
    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.2011-12-25
  • 0
    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).2011-12-25
  • 2
    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)\}$.2011-12-25
  • 0
    @Justin: OK, I guessI didn't read your post carefully enough.2011-12-25
  • 0
    You might be interested in [Jim Propp](http://faculty.uml.edu/jpropp/)'s rotor-router model(s), if you are not familiar with them. (They're not the same thing, though.)2011-12-25
  • 0
    @Raskolnikov, cardinal: yes, the distribution depends on the direction you are facing.2011-12-25

1 Answers 1

9

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.

  • 0
    Thank you! I would mark this as answered, but not sure how.2011-12-26
  • 2
    Looks like you found how to... Nice question, by the way.2011-12-27