\nonstopmode
\documentclass{article}
 \usepackage{amssymb}
 \usepackage{amsmath}
 
\newcommand{\ruleOne}[2]{\arraycolsep=14pt\renewcommand{\arraystretch}{1.75}%
\begin{array}[c]{c}#1\\
    \hline\multicolumn{1}{c}{#2}
\end{array}}
\newcommand{\ruleTwo}[3]{\arraycolsep=14pt\renewcommand{\arraystretch}{1.75}%
\begin{array}[c]{lr}#1&#2\\
    \hline\multicolumn{2}{c}{#3}
\end{array}}
\newcommand{\ruleThree}[4]{\arraycolsep=14pt\renewcommand{\arraystretch}{1.75}%
\begin{array}[c]{lcr}#1&#2&#3\\
    \hline\multicolumn{3}{c}{#4}
\end{array}}

\newcommand{\Real}{{\sf I\kern-0.14emR}} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newtheorem{solution}{Definition}[solution]

\setcounter{section}{1}
\newtheorem{definition}{Definition}[section]
\newtheorem{solution}[definition]{Solution}

\newcommand{\proofcomplete}{\hspace*{\fill $\Box$}}
\newenvironment{proof}%
  {\begin{trivlist}\item[\hskip\labelsep{\normalsize\it Proof.}]}%
  {\proofcomplete \end{trivlist}}
\newcommand{\Comment}[1]{}

\begin{document}

\begin{center}
{\bf COURSE 336 \\ 
PERFORMANCE ANALYSIS\\
P.G. HARRISON \\
Coursework 3, 2006\\

Solution to assessed exercises \\
}
\end{center}
\section*{Solutions}


A  small shop has space for one customer only.  If the shop is empty, then  in
the next time-unit, either a 
customer arrives with probability  $\alpha$ or 
the shop remains empty.  If a customer has arrived,
 then the shop is full, and could either stay 
  full in the next time-unit or the  customer 
  could leave the shop  empty with probability $\beta$.
\begin{enumerate}
\item Describe the behaviour of the shop as a Discrete Time Markov Chain with two states
$1,2$ representing the two states of the shop: empty and full. Define  the one-step
transition probability  matrix $\mathbf{Q}$.

\begin{solution} 
The one-step transition probability  matrix $\mathbf{Q}$  is defined as follows:
 \[
 \mathbf{Q} = \left( \begin{array}{cc}
 1 - \alpha & \alpha \\
 \beta & 1-\beta \\
  \end{array}
  \right )\]
\end{solution}

\item Write down  the state probability vector at time $0$, assuming that initially
 the Markov Chain is in the empty state.  Calculate $q^{(2)}_{12}$ and 
 $q^{(2)}_{11}$.
 
 \begin{solution} 
The  state probability vector  when the state is empty (for sure) is $(1 \, \,0)$.

\item 
We calculate $q^{(2)}_{12}$ as follows:
  \[ \begin{array}{rcl}
 q^{(2)}_{12} & =& P(X_2 = 2 | X_0 = 1) \\
  & =& P(X_2=2 | X_1 = 1)P(X_1=1 | X_0 = 1)  + 
   P(X_2=2 | X_1 = 2)P(X_1=2 | X_0 = 1) \\
   & =& \alpha(1-\alpha) + \alpha(1- \beta)\\ 
   \end{array} \]
   
Similarly, we calculate $q^{(2)}_{11}$ as follows:
  \[ \begin{array}{rcl}
 q^{(2)}_{11} & =& P(X_2 = 1 | X_0 = 1) \\
  & =& P(X_2=1 | X_1 = 1)P(X_1=1 | X_0 = 1)  + 
   P(X_2=1 | X_1 = 2)P(X_1=2 | X_0 = 1\\
   & =& (1-\alpha)^2 + \alpha\beta)\\ 
   \end{array} \]
   Alternatively, 
  we simply calculate $\mathbf{Q}^2$
 \[
 \mathbf{Q}^2 = \left( \begin{array}{cc}
 1 - \alpha & \alpha \\
 \beta & 1-\beta \\
  \end{array}
  \right )   
  \left( \begin{array}{cc}
 1 - \alpha & \alpha \\
 \beta & 1-\beta \\
  \end{array}
  \right ) = \left( \begin{array}{cc}
 (1 - \alpha)^2 + \alpha\beta & \alpha(1-\alpha) + \alpha(1-\beta) \\
  \beta(1-\alpha)+ \beta^2 & \alpha\beta + (1-\beta)^2 \\
  \end{array}
  \right )  \]
  
Reading from the matrix above we have: 
  $q^{(2)}_{12} = \alpha(1 -\alpha) + \alpha(1-\beta) $ and 
  $q^{(2)}_{11} =(1 - \alpha)^2 + \alpha\beta $.
 
 \end{solution}

\item Write down  the state probability vector at time $0$, assuming that initially
 the Markov Chain is in the full state.  Calculate $q^{(2)}_{12}$ and 
 $q^{(2)}_{11}$.
 
\begin{solution}
The  state probability vector when the state is full is $(0 \,\,1)$.
 The rest is identical to the previous part. 
\end{solution}

\item Given the matrix  
$M = \left ( \begin{array}{rl} 1 & \alpha \\   
 1 & -\beta\end{array} 
 \right)$
 show that 
 $\mathbf{Q}M = M \left(\begin{array}{rl} 1 & 0\\ 	
 0& \omega\end{array} \right).$
 where $ \omega = 1 -\alpha -\beta$.
Hence show that, for $n \geq 0$

\[\begin{array}{rcl}\mathbf{Q}^{n}M = M  \left(\begin{array}{rl} 1 & 0\\ 			            		   
 0 & \omega^n\end{array} \right).
 \end{array}\]
 \begin{solution}
 \[ \begin{array}{rcl} \mathbf{Q}M = \left( \begin{array}{cc}
 1 - \alpha & \alpha \\
 \beta & 1-\beta \\
  \end{array}
  \right) \left ( \begin{array}{cc} 1 & \alpha \\   
 1 & -\beta \end{array} \right) 
 & =&
  \left ( \begin{array}{cc}  
  (1-\alpha)+ \alpha & (1- \alpha)\alpha - \alpha\beta  \\   
   \beta + (1-\beta)& \alpha\beta -(1-\beta)\beta 
   \end{array} \right) \\
   &&\\
  & = & \left ( \begin{array}{cc}  
  1 & \alpha(1- \alpha -\beta) \\   
   1& -\beta(1- \alpha -\beta)\\
    \end{array}
 \right) \\
 \end{array} \] 
 
 
 
 \[  M \left(\begin{array}{rl} 1 & 0\\ 	
 0& \omega\end{array} \right) = \left(\begin{array}{rl} 1 & \alpha \omega\\ 	
 1& -\beta \omega\end{array} \right) \] 
 \end{solution}
 Now,  observing that $\mathbf{Q} =M \left(\begin{array}{rl}
 1 & 0\\
 0 &\omega\\
 \end{array} \right) M^{-1}$,
 we prove by induction that  for all $n \geq 0$,
 $ \mathbf{Q}^n =M \left(\begin{array}{rl}
 1 & 0\\
 0 &\omega\\
 \end{array} \right)^n M^{-1}$, which is an equivalent statement.  

 \begin{description}
 \item[Base case] For $n=0$ (or 1), the result holds trivially (or from  what is given). 
 \item[inductive step]Assume that for $n \geq 1$ 
   \[ \mathbf{Q}^{n-1} =M \left(\begin{array}{rl}
 1 & 0\\
 0 &\omega\\
 \end{array} \right)^{n-1}. M^{-1}\]
 then, since $ \mathbf{Q}^{n} = \mathbf{Q}^{n-1}\mathbf{Q}$ we have
 \[\begin{array}{rcl}
 \mathbf{Q}^n & = & (M \mathbf{Q}^{n-1}M^{-1}) \mathbf{Q}\\
 & = &  (M\mathbf{Q}^{n-1}M^{-1})( M\mathbf{Q}M^{-1})\\ 
 &= & M\mathbf{Q}^{n} \mathbf{I} \mathbf{Q}M^{-1}\\
 & =& M \mathbf{Q}^n M^{-1}\\
 \end{array} \]
 where $\mathbf{I}$ is the identity matrix.
 \end{description}
\item Verify that the inverse of the matrix $M$ is
 $ \frac{1}{\alpha+ \beta} \left(\begin{array}{rl} \beta & \alpha\\
 1& -1\end{array} \right)$. Then show that:
 \[  \mathbf{Q}^{n}=  \frac{1}{\alpha + \beta}
\left(\begin{array}{rl} \beta+\alpha\omega^n & \alpha(1- \omega^n)\\
\beta(1-\omega^n)& \alpha + \beta\omega^n
\end{array} \right).\]

\begin{solution}
We have to show that:

\[ M \frac{1}{\alpha+ \beta} \left(\begin{array}{cc} \beta & \alpha\\
 1& -1\end{array} \right) = \left(\begin{array}{cc} 1 & 0 \\
 0 & 1\end{array} \right) \]
In fact:
\[ \begin{array}{rcl}
M \frac{1}{\alpha+ \beta} \left(\begin{array}{cc} \beta & \alpha\\
 1& -1\end{array} \right) &= &
  \frac{1}{\alpha+ \beta} M \left(\begin{array}{cc} \beta & \alpha\\
 1& -1\end{array} \right)\\
 & = & \frac{1}{\alpha+ \beta}\left(\begin{array}{cc}
 \alpha+\beta & 0 \\
 0 & \alpha +\beta\end{array} \right) \\
 &= &\left(\begin{array}{cc} 1 & 0 \\
 0 & 1\end{array} \right) 
 \end{array}\]
 
 $ \mathbf{Q}^n = M \left(\begin{array}{cc}1 &0 \\
 0 &\omega^n\end{array}\right). M^{-1}$ and we have
 \[ M \left(\begin{array}{cc}1 &0 \\
 0 &\omega^n\end{array}\right). =\left(\begin{array}{cc}1 & \alpha\omega^n\\
 1&-\beta\omega^n\end{array}\right). .\]
 Thus, we conclude
 \[\begin{array}{rcl}
 \left(\begin{array}{cc}1 & \alpha\omega^n\\
 1&-\beta\omega^n\end{array}\right).\frac{1}{\alpha+ \beta}
 \left(\begin{array}{cc} \beta & \alpha\\
 1& -1\end{array} \right) &=& \frac{1}{\alpha +\beta}\left(\begin{array}{cc} \beta
 +\alpha\omega^n & \alpha -\alpha\omega^n\\
 \beta -\beta\omega^n& \alpha +\beta\omega^n\end{array}\right). \\
 &=&  \frac{1}{\alpha +\beta}\left(\begin{array}{cc} \beta
 +\alpha\omega^n & \alpha(1 - \omega^n)\\
 \beta(1-\omega^n)& \alpha +\beta\omega^n\end{array}\right). \\
 \\ 
 \end{array}\]
\end{solution}

\item   If  $-1  < \omega < 1 $ and $\mathbf{Q}^{\infty} $ is the limit of
 $\mathbf{Q}^{n} $ 
as $n \rightarrow \infty$, show that the rows   of $\mathbf{Q}^{\infty} $
 are the same $\vec{p}=(p_1,p_2)$ and satisfy $ \vec{p}=  \vec{p} .\mathbf{Q} $.
 %% where   and 
  %%$p_2= \lim_{n \rightarrow
 %%\infty} q^{(n)}_{12}$ and  $p_1= \lim_{n \rightarrow\infty} q^{(n)}_{21}$
  
For which values of $\alpha, \beta$ does $\mathbf{Q}^{n} $  not converge
 as   $n \rightarrow \infty$?
What property does the Markov chain exhibit? What 
is the significance of  case   $\omega=1$?

\begin{solution}
\[\begin{array}{rcl}
\lim\limits_{n \rightarrow \infty}\mathbf{Q}^n & = &
\frac{1}{\alpha+ \beta}
\lim\limits_{n\rightarrow \infty}\left(\begin{array}{rl} 
\beta+\alpha\omega^n & \alpha(1- \omega^n)\\
\beta(1-\omega^n) & \alpha+\beta\omega^n
\end{array}\right)  \\ \\
&=& \left(\begin{array}{rl} 
\frac{\beta}{\alpha +\beta} & \frac{\alpha}{\alpha + \beta} \\
\frac{\beta}{\alpha +\beta} & \frac{\alpha}{\alpha +\beta}\\
\end{array}\right)
\end{array}\]

It remains  to show that
$(\frac{\beta}{\alpha+\beta},\frac{\alpha}{\alpha+\beta})\mathbf{Q}= ‹
(\frac{\beta}{\alpha+\beta},\frac{\alpha}{\alpha+\beta})$:
\[ 
\begin{array}{rcl}
(\frac{\beta}{\alpha+\beta},\frac{\alpha}{\alpha+\beta})\mathbf{Q}&=& 
(\frac{\beta(1-\alpha)}{\alpha +\beta} + \frac{\alpha \beta}{\alpha + \beta},
\frac{\alpha\beta}{\alpha +\beta} + \frac{\alpha(1-\beta)}{\alpha +\beta})\\ \\
& = &
\frac{\beta  -\alpha\beta +\alpha\beta}{\alpha+\beta},\frac{\alpha +\alpha\beta
-\alpha\beta}{\alpha +\beta}\\ \\
& = & (\frac{\beta}{\alpha+\beta},\frac{\alpha}{\alpha+\beta})\\
\end{array}\]

If $\alpha =\beta=1$, then the matrix does not converge and the chain is
periodic. If $\omega =1$ then 
$\mathbf{Q}^n= \left(\begin{array}{rl} 
1& 0\\
0 & 1
\end{array}\right)$ and the chain is no longer irreducible.

\end{solution}
\end{enumerate}

\end{document}