5
$\begingroup$

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$?

Improve this question
$\endgroup$
5
  • $\begingroup$ this can be diractlly calculate by solve a equation come from markov property. $\endgroup$
    – katago
    Commented Nov 24, 2020 at 19:23
  • $\begingroup$ Well, on $\mathbb{Z}^2$ there is right, left, forward and back. $\endgroup$
    – Frederik Ravn Klausen
    Commented Nov 24, 2020 at 19:33
  • $\begingroup$ uh, what is the mean of turns right and left. it go through two lattice? $\endgroup$
    – katago
    Commented 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$
    – Frederik Ravn Klausen
    Commented 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$
    – Dieter Kadelka
    Commented Nov 24, 2020 at 21:59

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .