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

  • 2
    Looks like you found how to... Nice question, by the way.2011-12-27