# Recurrent graph

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.

-
This isn't my field, but can't you saw the ladder down the middle? That is, isn't a random walk on this graph equivalent to a random walk on the simpler graph (n), n∈Z, (n)~(n+1), with "pauses" when the walker on the original ladder would have passed between (1,n) and (2,n)? –  Beta Jul 26 '12 at 3:42
i don't know thats why i'm asking the question –  Christian Op Jul 26 '12 at 3:55

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.