Markov Chain: classify states of finite Markov chain I can easily see the states of this MC, recurrent and transient if I graph them, but how do I prove that a state is recurrent or transient. My book refers to probability to ever returning to state $j$ starting with $j$ to differentiate states.
STATES: 0,1,2,3,4
$$P =
\pmatrix{0&  0& 0.5 &0.5 &0 \\
0& 0.1& 0 &0.4 &0.5 \\
0.9 &0  &0.1 &0 &0\\
0 &0  &1 &0 &0\\
0.05 &0 &0.05 &0 &0.9\\}$$
From mathematica: recurrent states: {0,2,3}
Transient: {1},{4}
 A: Firstly separate the states in communication classes. There are two communication classes 
which are determined as follows.


*

*Start from state $0$. Which states can you visit and then return to state $0$? You can make following transitions $$0\xrightarrow{0.5} 2 \xrightarrow{0.9} 0$$ So $0$ and $2$ communicate, which means that they belong to the same communication class. In symbols $$0\leftrightarrow 2$$ In contrast if you make the transition $$0\xrightarrow{0.5} 3$$ then you can not return from state $3$. Therefore $0$ and $3$ belong to different communication classes. 

*Start from state $1$.  Which states can you visit and then return to state $1$? You can make following transitions $$1\xrightarrow{0.5} 4 \xrightarrow{0.05} 1$$ So $1$ and $4$ communicate, which means that they belong to the same communication class. In symbols $$1\leftrightarrow 4$$ In contrast if you make the transition $$1\xrightarrow{0.4} 3$$ then you can not return from state $3$. Therefore $1$ and $3$ belong to different communication classes.

*Do the classes $C_1=\{0,2\}$ and $C_2=\{1,4\}$ communicate? The answer is no, because starting from $C_1$ we can never go to $C_2$ but starting from $C_2$ we will land in $C_1$ eventually and never return. 

*Finally, state $3$ is absorbing, which means that whenever you go there you stay there for ever. So, this is the only recurrent state. 


In sum, classes $C_1=\{0,2\}$ and $C_2=\{1, 4\}$ are transient and $C_3=\{3\}$ is recurrent. To see that $C_1$ is transient and obviously in different class than state $3$ ask whether it is possible to visit $C_1$ for ever. The answer is no, since after landing for the first time in $C_3$ you will never return... By definition, see Wikipedia A state i is said to be transient if, given that we start in state i, there is a non-zero probability that we will never return to i.
A: There are some common (and very useful) results concerning recurrence and transitivity of states which you might know and/or could use:


*

*All states in an irreducible set are either all recurrent or all transient.

*State $i$ is transient if and only if
\begin{equation}
\sum_{n=1}^{\infty}p_{ii}^{(n)} < \infty
\end{equation}

*State $i$ is recurrent if and only if
\begin{equation}
\sum_{n=1}^{\infty}p_{ii}^{(n)} = \infty
\end{equation}
where $p_{ii}^{(n)} = P(X_n = i\,\,|\,\,X_0 = i)$. 

A: There is a simple algorithm: let $P$ the transition matrix.


*

*let $A=I + P$, $j = 1$

*replace each non $0$ entry by $1$

*replace $A$ by $A^2$, $j$ by $2j$

*Go back to $2.$ until $j\ge n$


Then the graph is connected iff every entry of $A$ is $1$.
At each iteration, at the end of step $4.$ the non zero entries of $A$ are the state you can go to with $\le j$ transitions.
