0
$\begingroup$

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?

  • 0
    @Ofir, but that property is not preserved by subgraphs (if the graphs in question are directed).2012-07-17

1 Answers 1

2

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.

  • 0
    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.2012-07-17