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
    What is your definition of "recurrent"?2012-07-17
  • 0
    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$.2012-07-17
  • 0
    @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$.2012-07-17
  • 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