Past exam of the mathematics course of the University of Cambridge / 2008 / ib / Paper 3 / 9H / Solution

A state of a Markov chain is a recurrent state if, starting there, the first strictly positive return time is finite with probability one. A recurrent Markov chain has every state recurrent; in an irreducible Markov chain recurrence is a class property. Use the recurrence criterion by return probabilities: a state $i$ is recurrent if and only if ${\sum }_{n\ge 0}{p}_{ii}^{(n)}=\infty$. To see the criterion, this sum is the expected number of visits including the initial one. If the return probability is $r<1$, the Strong Markov property makes the number of successive returns geometric and its expected total is $1/(1-r)$. If $r=1$, every fixed number of returns occurs with probability one, so the expectation is infinite.

For the symmetric simple random walk on the integers, odd-time return probabilities vanish, whileBy Stirling's formula, $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim 4^n/\sqrt{\pi n}$. Hence $p_{00}^{(2n)}\sim 1/\sqrt{\pi n}$, whose sum diverges. The return-probability criterion proves recurrence of zero. Translation invariance gives the same result at every integer, or one can use irreducibility. ThusThis proof establishes almost-sure return, not a finite expected return time; every state of the walk is in fact a null recurrent state.