Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

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

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.

share|cite|improve this answer

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.