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


{\bf Question}

\begin{description}
\item[(a)]
A Markov chain has the infinite transition probability matrix
given below. Classify the states, justifying your conclusions.
Find the mean recurrence time for any positive recurrent states.
(Label the states $1,\ 2,\ 3,\ \cdots$ in order.)

$\left(\begin{array}{cccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &
0 & 0 & . & . \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 & 0 & 0
& 0 & 0 & . & .\\  1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & .\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & . & .\\ 0 & 0 & 0 & 0 &
\frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 & . & . \\ 0 & 0 & 0 & 0
& \frac{2}{5} & 0 & \frac{3}{5} & 0 & 0 & 0 & . & .\\ 0 & 0 & 0 &
0 & \frac{2}{7} & 0 & 0 & \frac{5}{7} & 0 & 0 & . & . \\ 0 & 0 & 0
& 0 & \frac{2}{9} & 0 & 0 & 0 & \frac{7}{9} & 0 & . & .\\ 0 & 0 &
0 & 0 & \frac{2}{11} & 0 & 0 & 0 & 0 & \frac{9}{11} & . & .\\ . &
. & . & . & . & . & . & . & . & . & . & .\\. & . & . & . & . & . &
. & . & . & . & . & .\end{array}\right)$

\item[(b)]
Draw a transition diagram and write down the transition matrix for
a Markov chain having four intercommunicating positive recurrent
states each of period 3, and three intercommunicating transient
states.
\end{description}


\vspace{.25in}

{\bf Answer}
\begin{description}
\item[(a)]
\{1, 2\} forms a closed irreducible finite subchain, so that both
states are positive recurrent.  $\ds f_{22}^{(1)} = \frac{2}{3} >
0,$ so that both states are aperiodic.

\setlength{\unitlength}{.3in}
\begin{picture}(4,3)
\put(0.5,1.5){\circle{1}}

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

\put(2.5,1.5){\circle{1}}

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

\put(3.3,1.5){\circle{0.75}}

\put(3.65,1.4){\vector(0,-1){0}}

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

\put(.9,1.8){\line(1,0){1.2}}

\put(.9,1.8){\vector(1,0){.6}}

\put(0.9,1.2){\line(1,0){1.2}}

\put(2.1,1.2){\vector(-1,0){.6}}

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

\put(1.5,2.2){\makebox(0,0){1}}
\end{picture}

\begin{eqnarray*} \mu_2 & = & 1  \cdot \frac{2}{3} + 2 \cdot
\frac{4}{3}  = \frac{4}{3} \\ \mu_1 & = & 2 \cdot \frac{1}{3} + 3
\cdot \frac{2}{3} \cdot \frac{1}{3} + 4 \left(\frac{2}{3}
\right)^2 \cdot \frac{1}{3} + 5 \cdot \left( \frac{2}{3} \right)^3
\cdot \frac{1}{3} + .... \\ & = & \frac{2}{3} + \frac{1}{3} \left(
3 \cdot \frac{2}{3} + 4 \cdot \left( \frac{2}{3} \right)^2 + ...
\right) \end{eqnarray*}

\begin{itemize}
\item[either.]
\begin{eqnarray*} {\rm Let\ } s & = & 3 \frac{2}{3} +
4\left(\frac{2}{3}\right)^2 +5\left(\frac{2}{3}\right)^3+
...\\\frac{2}{3}s & = & 3\left(\frac{2}{3}\right)^2 +
4\left(\frac{2}{3}\right)^3 + ...\\ \frac{1}{3} s & = & 2 +
\left(\frac{2}{3}\right)^3+...\\ & = & \frac{1}{3} + 1 +
\frac{2}{3} + \left(\frac{2}{3}\right)^2 + ...\\ & = & \frac{1}{3}
+ \frac{1}{1 - \frac{2}{3}} = \frac{1}{3} + 3 \\ & = &
\frac{10}{3}  \\ \\ {\rm So\ \ } \mu_1& = & \frac{2}{3} +
\frac{1}{3} \cdot 10 = 4 \end{eqnarray*}

\item[or.]
$$\frac{1}{\mu_1}+ \frac{1}{\mu_2} = 1 \hspace{.2in}
\frac{1}{\mu_1} = \frac{1}{4}$$
\end{itemize}



State 3 is transient, leading to \{1, 2\} in one step.

State 4 is absorbing.

State \{5, 6, 7, ...\} form a closed irreducible subchain. $\ds
f_{55}^{(1)} = \frac{1}{3} >0.$ so they are all aperiodic.

Consider state 5.

The Markov chain can return to 5 at the nth step $(n>1)$ only via
the path $$5 \to 6 \to 7 \to ...\to 5+(n-1) \to 5$$

\begin{eqnarray*} {\rm So\ \ } f_{55}^{(n)} &=& \frac{2}{3} \cdot
\frac{3}{5} \cdot \frac{5}{7} \cdot \frac{7}{9} \cdots
\frac{2n-3}{2n-1} \cdot \frac{2}{2n+1} = \frac{4}{(2n-1)(2n+1)} \\
& = & \frac{2}{2n-1} - \frac{2}{2n+1} \\ {\rm So\ \ } f_{55} & = &
\frac{1}{3} + \sum_{n=2}^\infty \left( \frac{2}{2n-1} -
\frac{2}{2n+1} \right) = \frac{1}{3} + \frac{2}{3} = 1
\end{eqnarray*}

So state 5 is recurrent.

$$\mu_5 = \sum_{n=1}^\infty n f_{00}^{(n)} = \frac{1}{3} +
\sum_{n=2}^\infty \frac{n}{(2n-1)(2n+1)} = \infty$$

Thus states 5, 6, 7... are all null-recurrent.

\item[(b)]
Example

\setlength{\unitlength}{.3in}
\begin{picture}(5,10.5)
\put(0.5,0.5){\circle{1}}

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

\put(3.5,0.5){\circle{1}}

\put(3.5,0.5){\makebox(0,0){7}}

\put(1,0.5){\line(1,0){2}}

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

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

\put(2,3){\circle{1}}

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

\put(3.5,1){\line(-1,2){1}}

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

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

\put(1.5,3){\line(-1,-2){1}}

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

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

\put(2,6){\circle{1}}

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

\put(2,3.5){\line(0,1){2}}

\put(2,3.5){\vector(0,1){1}}

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

\put(2,10){\circle{1}}

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

\put(2,6.5){\line(0,1){3}}

\put(2,6.5){\vector(0,1){1.5}}

\put(2.3,8){\makebox(0,0){1}}

\put(3.5,8){\circle{1}}

\put(3.5,8){\makebox(0,0){2}}

\put(0.5,8){\circle{1}}

\put(0.5,8){\makebox(0,0){4}}

\put(.75,7.6){\line(1,-2){.75}}

\put(.75,7.6){\vector(1,-2){.4}}

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

\put(3.25,7.6){\line(-1,-2){.75}}

\put(3.25,7.6){\vector(-1,-2){.4}}

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

\put(2.4,9.75){\line(1,-2){0.75}}

\put(2.4,9.75){\vector(1,-2){0.4}}

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

\put(1.6,9.75){\line(-1,-2){0.75}}

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

\put(3,9.25){\makebox(0,0){$\frac{1}{2}$}}
\end{picture}

$$\left[\begin{array}{ccccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} &
0 & 0 & 0  \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0  & 0 & 0 & 0
& 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & 0 &
\frac{1}{2}& 0 \\ 0 & 0 & 0  & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1
&  0 & 0 \end{array}\right]$$

\end{description}



\end{document}
