Consider a random walk on $\mathbb{Z}^2$ which goes forward (i.e. takes a step in the same direction as the last step) with probability $p$ and turns right and left with probability $\frac{1-p}{2}$ respectively. Is it recurrent for all $1 > p \geq 0$?

  • $\begingroup$ this can be diractlly calculate by solve a equation come from markov property. $\endgroup$
    – katago
    Nov 24, 2020 at 19:23
  • $\begingroup$ Well, on $\mathbb{Z}^2$ there is right, left, forward and back. $\endgroup$ Nov 24, 2020 at 19:33
  • $\begingroup$ uh, what is the mean of turns right and left. it go through two lattice? $\endgroup$
    – katago
    Nov 24, 2020 at 19:35
  • $\begingroup$ Yes, it continues the same direction as the last step or it starts to walk in a new direction. $\endgroup$ Nov 24, 2020 at 19:44
  • 5
    $\begingroup$ This is an interesting example of a discrete time process, which is not a Markov chain. Of course it can be formulated as a Markov chain with state space f.i. $S = \mathbb{Z}^2 \times\{u,d,l,r\}$, with $u$ representing the upper direction, $\ldots$. The formulation of the transition law is a little bit cumbersome. I think that this MC is recurrent but I don't know. $\endgroup$ Nov 24, 2020 at 21:59

1 Answer 1


It looks like recurrence follows from Theorem 1 in Bender and Richmond, Correlated Random Walks, Ann. Probab. 12(1) (1984): 274–278 DOI:10.1214/aop/1176993392. (It gets late, though, so I may be getting something wrong.)

If $X_n$ is the "random walk" described in the question and $D_n$ is the "direction" in which the random walk is moving in step $n$, then $(D_n, X_{n+1} - X_n)$ is the "correlated random walk" according to the terminology of Bender and Richmond. Thus, we have to verify three conditions:

  • The "correlated random walk" is drift-free, that is, $\mathbb E|X_n| = o(n)$. This seems to follow from exponential convergence of the distribution of $D_n$ to the uniform distribution over four admissible directions.

  • Condition A holds: for some $d$ and $d'$, the support of the conditional distribution $X_{n+1} - X_n$ given $D_n = d$ and $D_{n+1} = d'$ is a linearly dense set in $\mathbb R^2$. This deepends on the exact definition of $X_n$, but even if this condition fails, the "correlated random walk" $(D_{2n}, X_{2n+2} - X_{2n})$ satisfies this condition.

  • Condition B holds: the Markov chain $D_n$ (or $D_{2n}$) is "strongly irreducible": this is clearly true.


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.