Does this modified random walk (2D) return with probability 1?

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?

• 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. – Raskolnikov Dec 25 '11 at 21:11
• 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). – Justin Gilmer Dec 25 '11 at 21:15
• 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)\}$. – cardinal Dec 25 '11 at 21:19
• @Justin: OK, I guessI didn't read your post carefully enough. – Raskolnikov Dec 25 '11 at 21:32
• 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.) – cardinal Dec 25 '11 at 21:33