= Solution
A state $i$ is recurrent if the probability of returning to $i$ at a strictly positive time, starting at $i$, equals one. It is transient if that probability is less than one. If $i$ and $j$ communicate, choose $r,s$ with $p_{ji}(r)>0$ and $p_{ij}(s)>0$. Chapman-Kolmogorov gives
$$
p_{jj}(r+n+s)\ge p_{ji}(r)p_{ii}(n)p_{ij}(s).
$$
If $i$ is recurrent, summing over $n$ makes the right-hand side diverge, so the allowed recurrence criterion proves $j$ recurrent. Interchanging $i,j$ proves recurrence is shared throughout a <communicating class>, and therefore transience is shared too.
For the <simple random walk>, an odd number of steps cannot return to its starting point, and
$$
p_{00}(2n)=\binom{2n}{n}[p(1-p)]^n\sim\frac{[4p(1-p)]^n}{\sqrt{\pi n}}.
$$
For $p=1/2$ the return series diverges like $\sum n^{-1/2}$, proving recurrence. For $0<p<1$, $p\ne1/2$, its tail is bounded by a convergent geometric series since $4p(1-p)<1$, proving transience. At $p=0$ or $1$ the walk is deterministic and never returns. Translation invariance transfers the conclusion to every state. Thus \b[recurrence holds exactly when $p=1/2$].
Back to article page
