Null-recurrence of a random walk 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)$
 A: 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$.
A: Let's try to show $0$ is null-recurrent. 
To get back to $0$, you have to do two $-1$s for every $+2$. So you have to take $3n$ steps, for some $n$, of which $n$ are $+2$s and $2n$ are $-1$s. The number of ways to do this is $3n\choose n$, and the probability of any one of these ways to get back to zero is $(1/3)^n(2/3)^{2n}$. So, now you know the probability of being at $0$ after $m$ steps. 
I was going to say that this allows you to calculate the expected number of steps to get back to zero, but then I realized that some of the ways to get back after, say, $6$ steps include ways where you were already back after $3$ steps, so some adjustment in the formulas will be necessary to take this into account. So this is more of a suggestion as to how to proceed than it is a complete outline of a procedure. 
Anyway, with some luck you'll be able to turn this into a proof that the expected time of return to $0$ is infinite, and then adjust the argument as necessary to show that every state is null-recurrent. 
A: One shall know that statement (not so obvious btw) :

for an irreducible chain $E \colon $ there exists a stationnary
distribution $\iff \exists i \in E$ such that $i$ is positive
recurrent $\iff  \forall i \in E$, $i$ is positive recurrent.

Here, I want to prove that the chain you mentionned can't have a stationary distribution. Of course, here I'm proving that the chain is not positive recurrent, but a simple argument proves that the chain is not transient.
It would be by using the difference equations. Your case is certainly not straight forward (as the length of the other answers suggest). So for the sake of understanding the method I'll simply consider the normal random walk ( $ P_{i,i+1} = \frac 1 2 = P_{i,i-1}$ ).
Let's assume that for the classic random walk, there exists a stationary distribution. Then it satisfies $$\forall j \in E :  \pi_j = \sum_{i \in E} \pi_i P_{i,j} = \frac 1 2 \pi_{j-1} + \frac 1 2  \pi_{j+1}$$
and we know how to solve such equations (difference equations). The answer is given by $$ \pi_j =  a + bj $$ with constants $a,b$. However, because of the "boundary" conditions :
$$\pi_j > 0, \forall j \implies b = 0, a > 0 $$
$$ \#E = \infty \implies \forall j, \pi_j \neq a > 0  $$
thus yielding that $ \pi $ does not exist.
