Originally Posted by

**pedrosorio** Hi, I was reading about Markov chains in wikipedia and I've got a doubt on this topic: Markov chain - Wikipedia, the free encyclopedia

More specifically, I wanted examples of transient and null recurrent states.

If I have a chain with 3 states that communicate with each other. I can start at state 1, and do something like 1->2->3->2->3->2->3->2->3... etc. Does this mean P(T1 = infinity) > 0? I don't think so, since calculating this over infinite time steps would yield a 0 probability, am I correct?

You have $\displaystyle P(T_1=\infty)=0$ indeed. Since $\displaystyle p_{21}>0$, if the state 2 is visited infinitely often, the Markov chain will also visit the state 1 infinitely often (if an event has positive probability and you procede to infinitely many independent trials, it will occur infinitely often).

With this argument, you can see that as soon as two states communicate with each other (i.e. there is a path with positive probability from one to another), if one is recurrent, then so is the other one. Thus you can gather the states into "recurrent classes", i.e. classes where the states communicate with each other. This helps to study the recurrence/transience since all states in the same class share the same status.

But the same chain with a 4th state that can only be accessed by state 1 and only accesses itself would make state 1 a transient state, right?

Right. 1 is transient, and so are 2 and 3 (they communicate with each other).

What about null recurrent states?

You won't be able to find null recurrent states with a finite number of states. Those are always positive recurrent (or transient). This is connected to the existence of a steady-state...

The most simple example of a null-recurrent Markov chain is the symmetric random walk on $\displaystyle \mathbb{Z}$: it is given at time $\displaystyle n$ by $\displaystyle S_n=\xi_1+\cdots+\xi_n$ where $\displaystyle \xi_1,\xi_2,\ldots$ are independent random variables with $\displaystyle P(\xi_i=1)=P(\xi_i=-1)=1/2$. Here's an elementary proof why it is null recurrent. First I prove that $\displaystyle E_0[T_1]=+\infty$ (time to go from 0 to 1). Either the first step is to the right, and $\displaystyle T_1=1$; or it is to the left, and the random walk now needs to go from -1 to 0 and then from 0 to 1. The time from -1 to 0 is the same as the time from 0 to 1, so we get:

$\displaystyle E_0[T_1]=\frac{1}{2}1+\frac{1}{2}(1+E_{-1}[T_0]+E_0[T_1])=\frac{1}{2}+E_0[T_1]$.

We get a contradition if $\displaystyle E_0[T_1]<\infty$. Now we deduce that $\displaystyle E_0[T_0]=+\infty$ as well. This is easy: after the first step, we are reduced to the previous problem (going from -1 to 0, or symmetrically from 1 to 0), so that

$\displaystyle E_0[T_0]=\frac{1}{2}E_{-1}[T_0]+\frac{1}{2}E_1[T_0]=E_0[T_1]=\infty$.

(A rigorous justification of the previous equalities would involve the Markov property)