Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
Nice. Stopping times are an interesting and strong technique. I still need to digest the solution, but I feel that I've seen those ideas in the past - we're decomposing the walk into parts and analyze each one with a simple stopping time. – Ofir Jul 17 '12 at 18:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.