In a random walk on $\mathbb{Z}$ starting at $0$, with probability 1/3 we go +2, with probability 2/3 we go -1. Please prove that all states in this Markov Chain are null-recurrent.
Thoughts: it is clear all states are inter-communicating, all with periodicity 3, therefore proving state 0 is null-recurrent is enough.
-
null-recurrence
-
One lengthy solution for simple random walk and null-recurrence
-
Where do I get stuck with 2/3, 1/3 unsymmetric random walk?
Cannot find a series expansion that simplifies the binomial form of $P_{ij}(s)$
Best Answer
If $0$ were transient, then the total number $N$ of visits to $0$ is a geometric random variable with $p=\mathbb{P}_0(T_0=\infty)>0$ (probability of escape). That's because each excursion from $0$ is independent, with probability $p$ of successfully escaping. In particular, the expected number of visits is finite: $\mathbb{E}(N)=1/p<\infty$.
On the other hand,
$$\mathbb{E}(N)=\mathbb{E}\left(\sum_{n=0}^\infty 1_{(X_n=0)}\right)=\sum_{n=0}^\infty p_n(0,0) =\sum_{n=0}^\infty {3n\choose n}\left({1\over 3}\right)^n \left({2\over 3}\right)^{2n}=\infty.$$ You can show this sum is infinite by using Stirling's formula to show that $${3n\choose n}\left({1\over 3}\right)^n \left({2\over 3}\right)^{2n}\sim {c\over \sqrt{n}}.$$ Therefore, the state $0$ is not transient, so it is recurrent.
There are a number of ways to show that state $0$ is null. In your problem, put $x=y=0$ in (5.2) from Section 5.5 of Probability: Theory and Examples (2nd edition) by Richard Durrett to get:
$${1\over n}\sum_{m=1}^n p_m(0,0) \to {\mathbb{P}_0(T_0<\infty)\over \mathbb{E}_0(T_0)}.\tag{5.2}$$
Also $p_m(0,0)\to0$ as $m\to \infty$, implies that the left hand side in (5.2) goes to zero as well, hence $\mathbb{P}_0(T_0<\infty)/\mathbb{E}_0(T_0)=0$. Since $\mathbb{P}_0(T_0<\infty)>0$ we conclude that $\mathbb{E}_0(T_0)=\infty$.