Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 1 / 20H / a / Solution

A Markov chain is irreducible if every state can reach every other state in finitely many steps with positive probability. It is a recurrent Markov chain if, starting at any state, it returns to that state with probability one; for an irreducible chain this property is shared by all states.

For the simple symmetric random walk on $\mathbb{Z}$, taking $|j-i|$ steps all in the appropriate direction reaches $j$ from $i$ with probability $2^{-|j-i|}>0$. Thus the chain is irreducible. Its return probabilities areBy Stirling formula, $p_{00}^{(2k)}\sim 1/\sqrt{\pi k}$, so their sum diverges. The standard recurrence criterion ${\sum }_{n\ge 0}{p}_{00}^{(n)}=\infty$ therefore proves the walk is recurrent.

The printed hint's constant is erroneous: the actual limit of $\sqrt{k}{p}_{00}^{(2k)}$ is $1/\sqrt{\pi }$. Its positivity is what the recurrence argument requires, but the reciprocal is necessary for the correct numerical value.