= Solution
For a planar <simple symmetric random walk> write its coordinates as $(S_n,T_n)$ and rotate to $(S_n+T_n,S_n-T_n)$. Each step now has four equally likely values $(1,1),(1,-1),(-1,1),(-1,-1)$. Thus the two rotated coordinates are independent one-dimensional <simple symmetric random walks>.
A return is impossible at odd times, and at time $2n$ its probability is
$$
p_{2n}(0,0)=\left(2^{-2n}\binom{2n}{n}\right)^2.
$$
For $n\geq2$, the supplied estimate gives $1/(4n)<p_{2n}(0,0)<1/n$. At $n=1$ the lower bound is actually equality, $p_2(0,0)=1/4$; this harmless strict-endpoint typo does not affect the argument. The <harmonic series> diverges, so the criterion proved above shows that the origin is recurrent, in the terminology of a <recurrent Markov chain>. Translation invariance gives the same conclusion for every state. The <Markov chain> is <irreducible>, so from any starting point it hits any fixed state almost surely and revisits it infinitely often. One can see the hitting assertion directly: repeated returns to the starting point give repeated positive-probability opportunities to follow a finite path to the target.
Back to article page
