Let $X$ be a symmetric random walk on $\mathcal{Z}$ with transition matrix elements
$p(x,y)=1/3$ if $|x-y|\leq1$ and $0$ otherwise.
I know this is a recurrent random walk since the expectation of the jump is zero (see, for example, Theorem 17.41 of Probability Theory by A. Klenke, 3rd version).
I would like to prove the recurrence of $X$ without the above result. Thus, I would like to prove that
$$
P_0[\tau^1_0<\infty]=1
$$
where $\tau^1_0=\inf\{n>0: X_n=0\}$ is the first return time.
My attempt
Using the Law of Total Probability (first step analysis):
$$
P_0[\tau^1_0<\infty]=\frac{1}{3}P_0[\tau^1_0<\infty|X_1=-1]+\frac{1}{3}P_0[\tau^1_0<\infty|X_1=0]+\frac{1}{3}P_0[\tau^1_0<\infty|X_1=1]
$$
By using the Markov property I obtained
$$
P_0[\tau^1_0<\infty]=\frac{1}{3}P_{-1}[\tau^1_0<\infty]+\frac{1}{3}+\frac{1}{3}P_{1}[\tau^1_0<\infty]
$$
How can I continue from here? I think this is an example of "recurrent equations" but I do not know how to set up the system to be solved.
Let me know if more details are needed. Thank you.
Best Answer
Let us now set $u_{k}:=\mathbb{P}\left(\tau_{0}^{1}<\infty\right)$. As you shown, $$ u_{0}=\frac{1}{3}+\frac{2}{3}u_{1}. $$ Note that $u_{-1}$ is not here anymore because $u_{1}=u_{-1}$ due to the symetrical behavior of the chain. But with the same idea you can also show $$ u_{1}=\frac{1}{3}+\frac{1}{3}u_{1}+\frac{1}{3}u_{2}\text{ and }u_{2}=\frac{1}{3}\left(u_{1}+u_{2}+u_{3}\right) $$ and more generally, for all $n\geq 2$ $$ u_{n}=\frac{1}{3}\left(u_{n-1}+u_{n}+u_{n+1}\right) \Leftrightarrow u_{n+1}-2u_{n}+u_{n-1}=0. $$ This is a linear recurrent sequence of order $2$. At the order $2$, it can be solved using the "characteristic equation" given by $x^{2}-2x+1=0$, and this entails that (see https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients) $$ u_{n}=A+B(n-1),\forall n\geq 1. $$ But since $0\leq u_{n}\leq 1$, the above equation for $u_{n}$ can not hold unless $B=0$. So, we get that $u_{n}=A$ for all $n\geq 1$. To conclude, you can for instance remark that, due to the invariance by translation of the model and the strong Markov property, you have $\mathbb{P}_{k}(\tau_{0}<\infty)= \mathbb{P}_{1}(\tau_{0}<\infty)^{k}$, so $1/3\leq A= A^{k}\leq 1$ which cannot be true unless $A=1$.