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


{\bf Question}

A white rat is put into the maze shown below.  The rat moves
through the compartments at random i.e. if there are $k$ ways to
leave a compartment he chooses each of these with probability
$\frac{1}{k}$.  Show that the number of the compartment occupied
by the rat after n moves is the state for this Markov chain. Write
down the transition probability matrix for this Markov chain and
identify the closed sets of states.  Hence classify the states as
null-recurrent or positive recurrent or transient and periodic or
aperiodic.  What is the effect of introducing a door between
compartments 2 and 5? \setlength{\unitlength}{1.in}
\begin{center}
\begin{picture}(3,1.7)
\put(0,0){\line(0,1){1.5}}

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

\put(0,1.5){\line(1,0){3}}

\put(3,0){\line(0,1){1.5}}

\put(1,0){\line(0,1){0.15}}

\put(1,0.35){\line(0,1){0.8}}

\put(1,1.35){\line(0,1){.15}}

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

\put(2,0.35){\line(0,1){0.8}}

\put(2,1.35){\line(0,1){.15}}

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

\put(0.7,0.5){\line(1,0){0.6}}

\put(1.7,0.5){\line(1,0){1.3}}

\put(0,1){\line(1,0){2.3}}

\put(2.7,1){\line(1,0){0.3}}

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

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

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

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

\put(1.5,0.8){\makebox(0,0){5}}

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

\put(0.5,.3){\makebox(0,0){7}}

\put(1.5,.3){\makebox(0,0){8}}

\put(2.5,.3){\makebox(0,0){9}}
\end{picture}
\end{center}

\vspace{.25in}

{\bf Answer}

The probabilities of moving from one compartment to another
depends only on which compartment the rat in occupying.  This is
the Markov propety.

The transition matrix is as follows:

\bigskip

$\begin{array}{ccccccccccc} \textit{\underline{\ \ TO\ \ }}  & 1 &
2 & 3 & 4 & & 5 & 6 & 7 & 8 & 9 \\ \textit{FROM} \\ 1 & 0 & 1 & 0
& 0 & \vdots & 0 & 0 & 0 & 0 & 0
\\ 2 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & \vdots & 0 & 0 & 0 & 0
& 0
\\ 3 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & \vdots & 0 & 0 & 0 & 0
& 0
\\ 4 & 0 & 0 & 1 & 0  & \vdots & 0 & 0 & 0 & 0 & 0 \\  &\cdots & \cdots &
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots &
\cdots  \\ 5 & 0 & 0 & 0 & 0 & \vdots & 0 & 0 & 0 & 1 & 0
\\ 6 & 0 & 0 & 0 & 0 & \vdots & 0 & 0 & 1 & 0 & 0 \\ 7 & 0 & 0 & 0 & 0  & \vdots & 0
& \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 8 & 0 & 0 & 0 & 0  & \vdots
& \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 9 & 0 & 0 & 0
& 0 & \vdots & 0 & 0 & 0 & 1 & 0 \end{array}$

There are two closed sets of states \{1,2,3,4\} and \{5,6,7,8,9\}.
All states are periodic with period 2.  Both closed sets form
irreducible Markov chains.  Hence by a theorem all states are
positive recurrent.

If we introduce a door between 2 and 5, all states
intercommunicate, so the whole Markov chain is infinite and
irreducible, and hence all states are positive recurrent.

The new matrix is

\bigskip
$\begin{array}{ccccccccccc} \textit{\underline{\ \ TO\ \ }}  & 1 &
2 & 3 & 4 & & 5 & 6 & 7 & 8 & 9 \\ \textit{FROM} \\ 1 & 0 & 1 & 0
& 0 & \vdots & 0 & 0 & 0 & 0 & 0\\  2 & \frac{1}{3} & 0 &
\frac{1}{3} & 0 & \vdots & \frac{1}{3} & 0 & 0 & 0 & 0 \\ 3 & 0 &
\frac{1}{2} & 0 & \frac{1}{2} & \vdots & 0 & 0 & 0 & 0 & 0 \\ 4 &
0 & 0 & 1 & 0  & \vdots & 0 & 0 & 0 & 0 & 0
\\ &\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots &
\cdots & \cdots & \cdots  \\ 5 & 0 & \frac{1}{2} & 0 & 0 & \vdots
& 0 & 0 & 0 & \frac{1}{2} & 0 \\ 6 & 0 & 0 & 0 & 0 & \vdots & 0 &
0 & 1 & 0 & 0 \\ 7 & 0 & 0 & 0 & 0  & \vdots & 0 & \frac{1}{2} & 0
& \frac{1}{2} & 0 \\ 8 & 0 & 0 & 0 & 0  & \vdots & \frac{1}{3} & 0
& \frac{1}{3} & 0 & \frac{1}{3} \\ 9 & 0 & 0 & 0 & 0 & \vdots & 0
& 0 & 0 & 1 & 0 \end{array}$

\bigskip

The results could be obtained by \lq \lq bare hands \rq \rq
methods but would be complicated.  Mean recurrence times are also
very complicated, especially for states 5 to 9.



\end{document}