% m211oh83.tex - A Rat Maze 
%   -revised Mar 2018: 3rd page added
%
\newcommand{\titlesize}{30pt} % for PcTeX fonts -usual: 30pt 
\input{m211oh.tex}
%\input{m211ohwo.tex}
%
\vspace*{-30pt}
\begin{center}\tcr{\rmH A Rat Maze} 
\end{center} %\vspace{0pt}
%\LARGE              
\huge

%\begin{description}  
Consider the following \tcr{system of three chambers} connected by \tcg{passages} as shown. 
% At time $t_0$, a rat is placed in one of the chambers (say in chamber 1).
\vspace{5pt}

\noi\begin{minipage}{8cm}
\setlength{\unitlength}{1.5mm}
\vspace*{10pt}

\noi\begin{picture}(50,50)
% 1st box
\put(10,40){\line(1,0){3.5}}
\put(16.5,40){\line(1,0){3.5}}
\put(10,40){\line(0,1){10}}
\put(10,50){\line(1,0){10}}
\put(20,40){\line(0,1){3.5}}
\put(20,46.5){\line(0,1){3.5}}
\put(15,45){\makebox(0,0){1}}
% 2nd box:
\put(40,25){\line(1,0){3.5}}
\put(46.5,25){\line(1,0){3.5}}
\put(40,25){\line(0,1){10}}
\put(40,35){\line(1,0){3.5}}
\put(46.5,35){\line(1,0){3.5}}
\put(50,25){\line(0,1){10}}
\put(45,30){\makebox(0,0){2}}
% 3rd box:
\put(10,10){\line(1,0){10}}
\put(10,10){\line(0,1){10}}
%\put(20,10){\line(0,1){10}}
\put(20,10){\line(0,1){1.5}}
\put(20,14.5){\line(0,1){1}}
\put(20,18.5){\line(0,1){1.5}}
%\put(10,20){\line(1,0){10}}
\put(10,20){\line(1,0){3.5}}
%\put(14,20){\line(1,0){1}}
\put(16.5,20){\line(1,0){3.5}}
\put(15,15){\makebox(0,0){3}}
% lines box 1/3
\put(13.5,20){\line(0,1){20}}
\put(16.5,20){\line(0,1){20}}
% lines box 1/2
\put(20,43.5){\line(1,0){23.5}}
\put(20,46.5){\line(1,0){26.5}}
\put(43.5,35){\line(0,1){8.5}}
\put(46.5,35){\line(0,1){11.5}}
% lines box 2/3
\put(20,11.5){\line(1,0){26.5}}
\put(20,14.5){\line(1,0){23.5}}
\put(20,15.5){\line(1,0){23.5}}
\put(20,18.5){\line(1,0){23.5}}
\put(43.5,14.5){\line(0,1){1}}
\put(43.5,18.5){\line(0,1){6.5}}
\put(46.5,11.5){\line(0,1){13.5}}
\end{picture}
%\end{minipage}
\end{minipage}
\begin{minipage}{10cm}
\vspace*{-25pt}
\noi At time \mc{t = 0}, a rat is placed in one of the chambers (say in \tcg{chamber} \mc{1}).
\end{minipage}\vspace{-25pt}

\noi \tcg{Each minute thereafter}, the rat \tcr{is driven out} of its present chamber by some stimulus and is prevented from re-entering immediately.

\noi \tcr{Assume:} the rat \tcr{chooses} the exits of each chamber \tcr{at random}.
%\end{minipage}
%\vspace{-20pt}\vspace{5pt}
\sps

\noi {\tcr{\bf Question:}} What is the \tcg{probability} that the rat is in a certain chamber after \mc{n} minutes?
\sps

\noi \tcr{{\bf Note:}} If \mc{s_i} denotes the \tcg{state} that the rat is in chamber \mc{i}, then we have a \tcr{Markov chain} with \vspace{-15pt}\tcr{transition matrix}
\tcb{$$
\exprow{1.2}
A=\left(\begin{array}{ccc}
0&\frac{1}{2}&\frac{1}{3}\\
\frac{1}{2}&0&\frac{2}{3}\\
\frac{1}{2}&\frac{1}{2}&0
\end{array}\right). 
\exprow{1.0}
$$}

\iffalse
 Put
\mc{\vec{v}_n = (v_{{\scr1},n},v_{{\scr2},n},v_{{\scr3},n})^t} where
\mc{\vec{v}_{i,n}} denotes the probability that the rat is in chamber \mc{i} after \mc{n} minutes.

$\begin{array}{rcl}
\vec{v}_{1,n}&=&\parbox[t]{14cm}{the probability that the rat is in chamber  1 after $n$ minutes}\\
\vec{v}_{2,n}&=&\parbox[t]{14cm}{the probability that the rat is in chamber  2 after $n$ minutes}\\
\vec{v}_{3,n}&=&\parbox[t]{14cm}{the probability that the rat is in chamber  3 after $n$ minutes}
\end{array}$
\spm

\noi Then, if we put $\vec{v}_n = (v_{1,n},v_{2,n},v_{3,n})^t$, we have the Markov chain
$$
\vec{v}_{n+1} = A\vec{v}_n\quad\mbox{with}\; \vec{v}_0 = (1,0,0)^t,
$$
\fi

\noi\tcr{\bf Analysis:} By definition, the \mc{ij}-th entry \mc{a_{ij}} of 
the \tcr{transition matrix} \mc{A=(a_{ij})} is the probability that the rat goes from chamber \mc{j} to  chamber \mc{i}. %To compute $A$, we note:
\spm

\noi\tcr{\bf Now:} If the rat \ldots
\sps

\exprow{1.3}\expcol{-2pt}
\noi$\begin{array}{rl}
\mbox{\ldots is in \tcr{chamber 1:}}&\parbox[t]{11.95cm}{\tcg{chambers 2} and \tcg{3} are \tcr{equally likely}}
\\ 
& \tcr{\Rightarrow} \mbox{the probability is  \mc{\frac{1}{2}, \frac{1}{2}} each,} \\
 & \tcr{\Rightarrow} \tcb{a_{\scr21}=a_{\scr31}=\frac{1}{2}};\\
\mbox{\ldots is in \tcr{chamber 2:}}&\parbox[t]{11.95cm}{\tcg{chambers 1} and \tcg{3} are \tcr{equally likely}}\\
 & \tcr{\Rightarrow} \mbox{the probability is \mc{\frac{1}{2}, \frac{1}{2}} each,} \\
 & \tcr{\Rightarrow} \tcb{a_{\scr12}=a_{\scr32}=\frac{1}{2}};\\
\mbox{\ldots is in \tcr{chamber 3:}}& 
\parbox[t]{11.95cm}{there are \mc{2} exits to \tcg{chamber 2} and \mc{1} exit to \tcg{chamber 1}} \\ 
 & \tcr{\Rightarrow} \parbox[t]{11.0cm}{\tcg{chamber 2} is \tcr{twice} as likely as \tcg{chamber 1},}\\
& \tcr{\Rightarrow} \tcb{a_{\scr13}=\frac{1}{3}, a_{\scr23}=\frac{2}{3}}.
\end{array}$
\exprow{1.0}\expcol{2pt}
\spm

\noi\tcr{\bf Thus,} this is a Markov chain with transition matrix 
\tcb{$$
\exprow{1.2}
A=\left(\begin{array}{ccc}
0&\frac{1}{2}&\frac{1}{3}\\
\frac{1}{2}&0&\frac{2}{3}\\
\frac{1}{2}&\frac{1}{2}&0
\end{array}\right). 
\exprow{1.0}
$$}

\iffalse
which is clearly stochastic, and hence we have the Markov chain 
$$
\vec{v}_{n+1}=A\vec{v}_n.
$$
\fi

%\newpage
\noindent More explicitly, if 
\mc{v_{n,i}} denotes the probability that the rat is in chamber \mc{i} at time \mc{t=n},
and if 
$$
\tcb{\vec v_n\; =\; (v_{n,1}, v_{n,2},v_{n,3})^t} 
$$
is the associated \tcr{probability distribution vector,} then we have the 
\tcr{Markov chain}
$$
\tcb{\vec v_{n+1}\; =\; A\vec v_n,}\quad \mbox{and so}\quad \tcb{\vec v_n = A^n\vec v_0}. 
$$
Since \mc{A} has characteristic polynomial
$$
\tcb{\mbox{ch}_A(t) \;=\; t^3 - \tfrac34t - \tfrac14 \;=\; (t-1)(t+\tfrac12)^2,}  
$$
the \tcr{Spectral Decomposition Theorem} shows that 
\begin{eqnarray*}
\tcb{A^n} & \tcb{=} & \tcb{E_{10} + \left(-\tfrac12\right)^nE_{20} + n\left(-\tfrac12\right)^{n-1}E_{21}} \\
&\tcb{=}& \tcb{E_{10} +  \left(-\tfrac12\right)^n(E_{20} - 2nE_{21}),}
\end{eqnarray*}
where the \tcr{constituent matrices} \mc{E_{ik}} are given by  
\large
$$
\tcb{E_{10} = \tfrac1{27}\left(\begin{array}{ccc}
8 & 8 & 8\\ 10 & 10 & 10\\ 9 & 9 & 9
\end{array}\right),\quad
E_{20} = \tfrac1{27}\left(\begin{array}{rrr}
19 & -8 & -8\\ -10 & 17 & -10\\ -9 & -9 & 18
\end{array}\right),\quad
E_{21} = \tfrac1{18}\left(\begin{array}{rrr}
1 & 1 & -2\\ -1 & -1 & 2\\ 0 & 0 & 0
\end{array}\right).}
$$
\huge
Thus, if \mc{\vec v_0 = (1,0,0)^t}, then  
$$
\tcb{\vec v_n = \tfrac1{27}\left(\left(\begin{array}{c}8\\10\\9\end{array}\right)
+ \left(-\tfrac12\right)^n\left(\begin{array}{c}19-3n\\3n-10\\-9\end{array}\right)
\right).}
$$
%\end{description} 
\end{document}                          