# A random walk on $\mathbb{Z}$ with a twist

I am trying to decide whether the following random walk is recurrent or not. Intuitively, I think it is - but I am not familiar with techniques of proving it.

My random walk is the following: on each point $i$, I can turn to $i-1$ with probability $\frac{1}{3}$, to $i+1$ with probability $\frac{1}{3}$, and with probability $\frac{1}{3}$ I jump to some recurrent graph $G_i$ (meaning $G_i$ contains the vertex $i$ and other vertices not in $\mathbb{Z}$).

For example, the $G_i$'s can be copies of $\mathbb{Z}$, and then we can think of my walk as a walk on $\mathbb{Z}^2$ where $(i,j)$ is connected to $(i',j')$ iff $j=j'=0,i' = i\pm 1$ or $i'=i, j'=j\pm 1$. This graph is recurrent (since it's a subgraph of the standard $\mathbb{Z}^2$ graph, which is recurrent).

So, is my intuition correct and the walk should be recurrent? And if not, what stronger conditions can I ask from the $G_i$'s for it to be recurrent?

-
What is your definition of "recurrent"? – Henning Makholm Jul 17 '12 at 18:22
So with non-zero probability you end up in some other unspecified graph - and does "recurrent" in that context mean returns to the origin with probability 1? And think about how many steps this takes in $G_i$. – Mark Bennet Jul 17 '12 at 18:25
@HenningMakholm It means that a random walk starting on $x$ returns to $x$ with probability 1. It doesn't matter which $x$ I choose, because my graph is connected, and a well-known theorem states that if a connected graph is recurrent with respect to some vertex, then the random walk starting on $x$ will reach $y$ with probability 1, for any $x,y$. – Ofir Jul 17 '12 at 18:25
@Ofir, but that property is not preserved by subgraphs (if the graphs in question are directed). – Henning Makholm Jul 17 '12 at 18:43

Let $(X_n)_{n\geqslant0}$ denote this random walk. Define recursively a sequence $(t(n))_{n\geqslant0}$ of stopping times by $t(-1)=-1$ and, for every $n\geqslant0$, $t(n)=\inf\{k\geqslant1+t(n-1)\mid X_k\in\mathbb Z\}$. Every graph $G_i$ is recurrent hence every $t(n)$ is almost surely finite. Let $Y_n=X(t_n)$. Then $(Y_n)_{n\geqslant0}$ performs a random walk on $\mathbb Z$ which, when at $i$, jumps to $i-1$, $i$ or $i+1$, with equal probabilities $\frac13$. Thus, $(Y_n)_{n\geqslant0}$ is recurrent, hence there exists infinitely many finite times $(s(n))_{n\geqslant0}$ such that $Y_{s(n)}=0$, say. For every $n$, $X(t_{s(n)})=0$, in particular $(X_n)_{n\geqslant0}$ is recurrent.
Note that as soon as one graph $G_i$ is transient, the argument above breaks down, and, in fact, $(X_n)_{n\geqslant0}$ becomes transient.