Let A be the infinite ladder graph in ${\bf Z}^2$ of the form $(1,n), (2,n)$ where $n\in{\bf Z}$ with edges defined by $(1,n)∼(2,n),(1,n)∼(1,n+1),(2,n)∼(2,n+1)$. Show that a simple random walk on A is recurrent.
Recurrent graph
1
$\begingroup$
probability
combinatorics
-
0i don't know thats why i'm asking the question – 2012-07-26
1 Answers
4
We can write the steps of the simple random walk on A as $Z_n\in\{+1,0,-1\}$ (equiprobable), where $+1$ means $(k,n)\rightarrow(k,n+1)$, $-1$ means $(k,n)\rightarrow(k,n-1)$ and $0$ means $(1,n)\leftrightarrow(2,n)$.
If we consider only $x_1$, then $S_n = \sum_{j=1}^n Z_n$. We can drop the $Z=0$ terms (which converge to 1/3 of the total) and get a 1-dimensional simple random walk in Z, which is known to be recurrent. If we consider only $x_0$ we can drop all but the $Z=0$ terms and get a two-state system that flips often and converges to 50-50 occupancy, independent of the walk on Z. Therefore as $n$ increases, the simple random walk on A will revisit every node a limitlessly increasing number of times, therefore it is recurrent.