Consider the following discrete-time random walk on $\mathbb Z$: where at location $n\in\mathbb Z$, the walker has probability $q_n$ of taking one step left, probability pn of taking one step right, and probability $r_n$ of staying at the same location. Of course for every $n$, $p_n+q_n+r_n=1$. I refer to this triple $(p_n,q_n,r_n)$ as a coin of the random walk at location n

Let $X_t$ be the position of the random walker at time $t$ ($t$ is a positive integer). I say that a random walk is recurrent if $\limsup_{t\to\infty} X_t=+\infty$ with probability $1$ and $\liminf_ {t\to\infty} X_t=-\infty$ with probability $1$. I say that a random walk is transient if $\lim_{t\to\infty} X_t=\infty$ with probability $1$ or $\lim _{t\to\infty} X_t=-\infty$ with probability $1$.

I would like the following statement to be true:

Consider a random walk on $\mathbb Z$ with coin at location $n$ given as $(p_n,q_n,r_n)$ and a random walk on $\mathbb Z$ with coin at location n given as $(\frac{p_n}{p_n+q_n},\frac{q_n}{p_n+q_n},0)$. Assume that the sequence $r_n$ is uniformly bounded away from $1$, and that the $p_n,q_n$ are uniformly bounded away from $0$ and $1$. Then the first random walk is recurrent if and only if the second is, and the first random walk is transient if and only if the second is.

My intuition is that when we are calculating recurrence/transience, we can more or less ignore the possibility that the walker stays put. When the walker is at location n, we are only interested whether the walker goes left or right next, and whether that transition happens after 1 time step or after 1000 time steps is irrelevant when considering recurrence/transience. Is this intuition correct, and if it is, is there a way to make it rigorous?


Yes. Your intuition is correct. One can consider the "jump chain" $(Y_n)$, that only updates when $X_n$ moves. That is we set $N_k=\min\{n>N_{k-1}\colon X_n\ne X_{n-1}\}$ and set $Y_k=X_{N_k}$. The Markov property for $(X_n)$ can be seen to imply that $(Y_k)$ is also a Markov chain. Further, the transition probabilities for $(Y_k)$ are exactly the $(\frac{p_n}{p_n+q_n},\frac{q_n}{p_n+q_n},0)$ that you wrote down. It's clear that for a particular realization (= random sequence $(X_n)_{n=1}^\infty$), and for the corresponding realization of the jump chain, one has $\limsup_{n\to\infty}X_n=\limsup_{k\to\infty} Y_k$ and $\liminf_{n\to\infty}X_n=\liminf_{k\to\infty}Y_k$. So $(X_n)$ is recurrent if and only if $(Y_k)$ is recurrent.

  • $\begingroup$ You are right, since the question asked about "random walk", I confused the meaning of $n$ in $(p_n, q_n, r_n) $. The question is indeed about a Markov chain, not a random walk. Actually, the assumption of $r_n$ separated from $1$ isn't needed; $r_n<1$ is enough. $\endgroup$ – zhoraster Mar 28 at 6:03
  • $\begingroup$ While I also think the conclusion is true, this argument only shows one direction, right? I.e. If $X_n$ is recurrent (or transient), then $Y_n$ is also recurrent (respectively, transient). But does it show the other direction? It would show the other direction if every chain is either recurrent or transient, but is that obvious? In particular, isn't that where $r_n<c<1$ is needed? If $r_n< 1$ only, might it be possible that, by some Borel-Cantelli argument, the position does not change infinitely often? Or am I missing something "obvious" and the proof is actually complete as it stands? $\endgroup$ – antkam Mar 28 at 11:47
  • $\begingroup$ It’s a basic fact about Markov chains that every irreducible Markov chain is either transient or recurrent $\endgroup$ – anthonyquas Mar 28 at 16:05
  • $\begingroup$ @anthonyquas - thanks! That's indeed the "obvious" that I was missing. :) I think I might have known that at some point (during grad school, many years ago) but forgot. Also I didn't quite recognize the OP's definition of recurrent and transient compared to the ones I vaguely recall. $\endgroup$ – antkam Mar 28 at 18:15

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.