= 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\ge0}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, while
$$
p_{00}^{(2n)}=\binom{2n}{n}2^{-2n}.
$$
By <Stirling's formula>, $\binom{2n}{n}\sim4^n/\sqrt{\pi n}$. Hence $p_{00}^{(2n)}\sim1/\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. Thus
$$
\boxed{\text{the symmetric simple random walk on }\mathbb Z\text{ is recurrent}.}
$$
This proof establishes almost-sure return, not a finite expected return time; every state of the walk is in fact a <null recurrent state>.
Back to article page
