\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

Classify as transient, null-recurrent or positive recurrent the
states of the Markov chains with the following transition
probability matrices:
\begin{description}
\item[(a)] $\ds \hspace{1in}P = \left( \begin{array}{ccc} 0 & \frac{1}{2} &
\frac{1}{2}\\ \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} &
\frac{1}{2} & 0 \end{array} \right),$
\item[(b)] $\ds \hspace{1in}P = \left( \begin{array}{cccc} 0 & 0 & \frac{1}{2} &
\frac{1}{2}\\ 1 & 0 & 0  & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0
\end{array} \right)$
\end{description}



\vspace{.25in}

{\bf Answer}

\begin{description}
\item[(i)]
Clearly from symmetry each state is of the same type. Return to
state 1 may be achieved by two sets of routes:

\setlength{\unitlength}{.5in}
\begin{picture}(8,3)
\put(0,2.5){\makebox(0,0){1}}

\put(0.1,2.5){\vector(1,0){.5}}

\put(0.8,2.5){\makebox(0,0){2}}

\put(1,2.5){\vector(2,1){.5}}

\put(1,2.5){\vector(2,-1){0.5}}

\put(1.6,2.75){\makebox(0,0){1}}

\put(1.65,2.25){\makebox(0,0){3}}

\put(1.8,2.25){\vector(2,1){.5}}

\put(1.8,2.25){\vector(2,-1){0.5}}

\put(2.4,2.5){\makebox(0,0){1}}

\put(2.4,2){\makebox(0,0){2}}

\put(2.6,2){\vector(2,1){.5}}

\put(2.6,2){\vector(2,-1){0.5}}

\put(3.3,2.25){\makebox(0,0){1}}

\put(3.3,1.75){\makebox(0,0){3}}

\put(3.4,1.75){\vector(2,1){.5}}

\put(3.4,1.75){\vector(2,-1){0.5}}

\put(4,2){\makebox(0,0){1}}

\put(4,1.5){\makebox(0,0)[l]{etc..}}

\put(4.5,2.5){\makebox(0,0){or}}

\put(5,2.5){\makebox(0,0){1}}

\put(5.1,2.5){\vector(1,0){.5}}

\put(5.8,2.5){\makebox(0,0){3}}

\put(6,2.5){\vector(2,1){.5}}

\put(6,2.5){\vector(2,-1){0.5}}

\put(6.6,2.75){\makebox(0,0){1}}

\put(6.65,2.25){\makebox(0,0){2}}

\put(6.8,2.25){\vector(2,1){.5}}

\put(6.8,2.25){\vector(2,-1){0.5}}

\put(7.4,2.5){\makebox(0,0){1}}

\put(7.4,2){\makebox(0,0){3}}

\put(7.6,2){\vector(2,1){.5}}

\put(7.6,2){\vector(2,-1){0.5}}

\put(8.3,2.25){\makebox(0,0){1}}

\put(8.3,1.75){\makebox(0,0){2}}

\put(8.4,1.75){\vector(2,1){.5}}

\put(8.4,1.75){\vector(2,-1){0.5}}

\put(9,2){\makebox(0,0){1}}

\put(9,1.5){\makebox(0,0)[l]{etc..}}


\end{picture}

So $f_{11} = 2\left( \left(\frac{1}{2}\right)^2 +
\left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 +
...\right) = 1$

The mean recurrence time is given by \begin{eqnarray*}\mu_1 & = &
1 \cdot 0 + 2 \cdot 2\cdot \left(\frac{1}{2}\right)^2 + 3 \cdot 2
\cdot \left(\frac{1}{2}\right)^3 + 4 \cdot  2 \cdot
\left(\frac{1}{2}\right)^4 + \ldots
\\ & = & 2 \cdot \frac{1}{2} + 3 \cdot \left(\frac{1}{2}\right)^2 +
4\cdot\left( \frac{1}{2}\right)^3 + \ldots
\end{eqnarray*} Note that $\frac{1}{2}\mu_1 = 2 \cdot\left( \frac{1}{2}\right)^2 +
3 \cdot \left(\frac{1}{2}\right)^3 + \ldots$

so $\ds \mu_1 - \frac{1}{2} \mu_1 = 1 + \left(\frac{1}{2}\right)^2
+ \left(\frac{1}{2}\right)^3 + \ldots = \frac{3}{2}$ so $\ds \mu_1
= 3$

Thus state 1 is positive recurrent and similarly states 2 and 3
are positive recurrent with $\mu = 3$

\newpage
\item[(ii)]
Transition diagram

\begin{center}
\setlength{\unitlength}{.75in}
\begin{picture}(4,2)
\put(0.5,1){\circle{.5}}

\put(0.5,1){\makebox(0,0){1}}

\put(.75,1.1){\vector(2,1){1}}

\put(0.75,0.9){\vector(2,-1){1}}

\put(2,1.6){\circle{.5}}

\put(2,1.6){\makebox(0,0){3}}

\put(2,0.3){\circle{.5}}

\put(2,0.3){\makebox(0,0){4}}

\put(2.3,0.3){\vector(2,1){1}}

\put(2.3,1.6){\vector(2,-1){1}}

\put(3.55,1){\circle{.5}}

\put(3.55,1){\makebox(0,0){2}}

\put(3.25,1){\vector(-1,0){2.5}}

\put(1,1.5){\makebox(0,0){$\frac{1}{2}$}}

\put(1,.5){\makebox(0,0){$\frac{1}{2}$}}

\put(2,1.1){\makebox(0,0){1}}

\put(2.9,1.5){\makebox(0,0){1}}

\put(2.9,.35){\makebox(0,0){1}}

\end{picture}
\end{center}

There are two return routes $1\rightarrow 1$, namely $ 1
\rightarrow 3 \rightarrow 2 \rightarrow 1$ and $ 1 \rightarrow 4
\rightarrow 2 \rightarrow 1.$

So $\ds f_{11} = \frac{1}{2} \cdot 1 \cdot 1 + \frac{1}{2} \cdot 1
\cdot 1  = 1$

The recurrence time for each rout is 3 so $\mu_1 = 3$

So $\ds f_{22} = \underbrace {1 \cdot \frac{1}{2} \cdot
1}_{2-1-3-2} \hspace{.1in} + \hspace{.1in} \underbrace{1 \cdot
\frac{1}{2} \cdot 1}_{2-1-4-2} = 1$ \hspace{.2in}Again $\mu_2 = 3$



So $\ds f_{33} = \underbrace {1 \cdot 1 \cdot \frac{1}{2}
}_{3-2-1-3} \hspace{.1in} + \hspace{.1in} \underbrace{1 \cdot 1
\cdot \frac{1}{2} \cdot 1 \cdot 1 \cdot
\frac{1}{2}}_{3-2-1-4-2-1-3} \hspace{.1in} + \hspace{.1in}
\underbrace{\frac{1}{2}^3 + \frac{1}{2}^4+\ldots}_{1-4-2 {\rm\
cycle}}  = 1$



$\ds \mu_3 = 3 \cdot \frac{1}{2} + 6 \cdot \frac{1}{2}^2 + 9 \cdot
\frac{1}{2}^3 + \ldots 3\left[\frac{1}{2} + 2 \cdot \frac{1}{2}^2
+ 3 \cdot \frac{1}{2}^3 + \ldots \right] = 6 $

By symmetry $f_{44} = 1$ and $\mu_4 = 6$


\end{description}


\end{document}