= 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 are
$$
p_{00}^{(2k)}=\binom{2k}{k}2^{-2k},\qquad p_{00}^{(2k+1)}=0.
$$
By <Stirling formula>, $p_{00}^{(2k)}\sim1/\sqrt{\pi k}$, so their sum diverges. The standard recurrence criterion $\sum_{n\geq0}p_{00}^{(n)}=\infty$ therefore proves \b[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.
Back to article page
