# 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.

1. null-recurrence

2. One lengthy solution for simple random walk and null-recurrence

3. 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)$

-
What have you tried so far? What are you struggling with? –  Jonathan Christensen Jan 23 '13 at 22:02
@JonathanChristensen I can prove that in a symmetric random walk, all states are null-recurrent, by using the generating function and series expansion, my solution is too long to be posted. –  mez Jan 23 '13 at 23:06
What form do you get for $P_{ij}(s)$? –  Gerry Myerson Jan 24 '13 at 11:25
@GerryMyerson $$P_{ij}(s) = 1+\sum_{n=1}^\infty \binom{3n}{n}(2/3)^{2n}(1/3)^{n}$$ –  mez Jan 24 '13 at 13:02
The generating function for $3n\choose n$ is $f(x)=\sum_0^{\infty}{3n\choose n}x^n$. What you have written is $f(4/27)$. Some expressions for $f$ are given at oeis.org/A005809 - I do not know whether any of them will be helpful. –  Gerry Myerson Jan 24 '13 at 22:41

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$.

-
$$E(N) = \sum_{n=0}^\infty n\cdot f_n(0,0)$$ where $f_n(0,0)$ denotes probability of first return to 0, we cannot use $p_n(0,0)$ because it causes multi-counting. To grasp $f_n(0,0)$ one way is to grasp its generating function $F(0,0)$ by exploiting its relation with $P(0,0)$ - the generating function of $p_n(0,0)$, so either I misunderstood your point or I have to disagree with you. Though the result I know is that 0 is null-recurrent. –  mez Jan 24 '13 at 19:17
The formula in your comment is wrong. The left hand side is the expected number of visits to zero, while the right hand side is the expected number of trials until the first return to zero. These are totally different. –  Byron Schmuland Jan 24 '13 at 19:32
Yes, that is what I wanted, to prove null-recurrence of states we need to show that expected time until return is infinite while possibility of eventual return is positive. I see we are talking about different things. –  mez Jan 24 '13 at 19:36
We are not talking about different things, but using different methods of proof. You don't need generating functions to show that a state is recurrent vs transient, or positive vs null. (My solution only does the first one). –  Byron Schmuland Jan 24 '13 at 20:49
yes. If you could help with the null-ness then it would be great coz that's mainly where i get stuck. –  mez Jan 24 '13 at 20:52

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.

-
I see your point and in fact I wan to post my solution (very long) for the problem of symmetric (1/2-1/2) random walk, then I can tell you where do I get stuck. But please wait for a while. –  mez Jan 24 '13 at 8:44
I have edited the question adding a solution to the 1/2-1/2 random walk example. Please help if you can. Thanks a lot. –  mez Jan 24 '13 at 11:04
To treat the double counting problem as you said, one way is to calculate the probability of first return and its generating function $F_{0,0}$, (by exploiting Markov property and derive a relation with $G_{0,0}$) –  mez Jan 24 '13 at 19:16