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?
Best Answer
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.