<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

\begin{description}
\item[(a)] A six state Markov chain has the probability transition
matrix $P$ given below.  Classify the states as positive
recurrent, null recurrent or transient.  Obtain the mean
recurrence times for all positive recurrent states. $$P = \left(
\begin{array}{cccccc} \frac{1}{2} &amp; \frac{1}{2} &amp; 0 &amp; 0 &amp; 0 &amp;0
\\ \frac{1}{3} &amp; \frac{2}{3} &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp;
\frac{1}{8}&amp; 0 &amp; \frac{7}{8} &amp; 0\\ \frac{1}{4} &amp; \frac{1}{4} &amp; 0 &amp;
0 &amp; \frac{1}{4} &amp; \frac{1}{4} \\ 0 &amp; 0 &amp; \frac{3}{4} &amp; 0 &amp;
\frac{1}{4} &amp; 0  \\ 0 &amp; \frac{1}{5} &amp; 0 &amp; \frac{1}{5} &amp;
\frac{1}{5} &amp; \frac{2}{5} \end{array}\right)$$
\item[(b)] Balls are thrown independently into $N$ boxes so that
each ball has a probability $\frac{1}{N}$ of falling into each
box.  Let $X_n$ be the number of empty boxes after $n$ balls have
been thrown.  Does $\{X_n\}\ \  n = 1, 2,\ldots$ form a Markov
chain? If $p_n$(k) denotes the probability that $X_n =  k$ show
that $$p_{n+1}(k) = \left(1 - \frac{k}{N}\right)p_n(k) +
\frac{k+1}{N}p_n(k+1) \hspace{.2in} {\rm for\ \ \ } k = 0,
1,\ldots, N-1$$
\end{description}



\vspace{.25in}

{\bf Answer}

\begin{description}
\item[(a)]
The transition matrix $P$ is: $$\begin{array}{c} 1 \\ 2 \\ 3 \\ 4
\\ 5
\\ 6
\end{array} \left(
\begin{array}{cccccc} \frac{1}{2} &amp; \frac{1}{2} &amp; 0 &amp; 0 &amp; 0 &amp;0
\\ \frac{1}{3} &amp; \frac{2}{3} &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp;
\frac{1}{8}&amp; 0 &amp; \frac{7}{8} &amp; 0\\ \frac{1}{4} &amp; \frac{1}{4} &amp; 0 &amp;
0 &amp; \frac{1}{4} &amp; \frac{1}{4} \\ 0 &amp; 0 &amp; \frac{3}{4} &amp; 0 &amp;
\frac{1}{4} &amp; 0  \\ 0 &amp; \frac{1}{5} &amp; 0 &amp; \frac{1}{5} &amp;
\frac{1}{5} &amp; \frac{2}{5} \end{array}\right)$$



\setlength{\unitlength}{.25in}
\begin{picture}(12,11)
\put(2.5,2.5){\circle{1}}

\put(2.5,2.5){\makebox(0,0)[c]{3}}

\put(1.6,2.5){\circle{0.75}}

\put(1.2,2.4){\vector(0,-1){0}}

\put(0.9,2.5){\makebox(0,0)[c]{$\frac{1}{8}$}}

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

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

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

\put(3,2.2){\vector(1,0){1.5}}

\put(4.5,1.5){\makebox(0,0){$\frac{7}{8}$}}

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

\put(6,2.8){\vector(-1,0){1.5}}

\put(4.5,3.5){\makebox(0,0){$\frac{3}{4}$}}

\put(6.5,1.6){\circle{.75}}

\put(6.6,1.2){\vector(1,0){0}}

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

\put(6.5,5.5){\circle{1}}

\put(6.5,5.5){\makebox(0,0){4}}

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

\put(6.5,5){\vector(0,-1){1}}

\put(6,4){\makebox(0,0)[c]{$\frac{1}{4}$}}

\put(10.5,5.5){\circle{1}}

\put(10.5,5.5){\makebox(0,0){6}}

\put(11.4,5.5){\circle{0.75}}

\put(11.8,5.4){\vector(0,-1){0}}

\put(12.2,5.5){\makebox(0,0){$\frac{2}{5}$}}

\put(10.1,5.9){\line(-1,1){3.25}}

\put(10.1,5.9){\vector(-1,1){1.5}}

\put(9.3,7.5){\makebox(0,0){$\frac{1}{5}$}}

\put(10.5,5){\line(-3,-2){3.5}}

\put(10.5,5){\vector(-3,-2){1.75}}

\put(9,3.4){\makebox(0,0){$\frac{1}{5}$}}

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

\put(7,5.2){\vector(1,0){1.5}}

\put(8.5,4.7){\makebox(0,0){$\frac{1}{4}$}}

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

\put(10,5.8){\vector(-1,0){1.5}}

\put(8.5,6.3){\makebox(0,0){$\frac{1}{5}$}}

\put(6.5,9.5){\circle{1}}

\put(6.5,9.5){\makebox(0,0){2}}

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

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

\put(6.9,7.5){\makebox(0,0){$\frac{1}{4}$}}

\put(7.4,9.5){\circle{0.75}}

\put(7.8,9.4){\vector(0,-1){0}}

\put(8.1,9.5){\makebox(0,0){$\frac{2}{3}$}}

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

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

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

\put(6,9.2){\vector(-1,0){1.5}}

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

\put(3,9.8){\vector(1,0){1.5}}

\put(4.5,8.6){\makebox(0,0){$\frac{1}{3}$}}

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

\put(1.6,9.5){\circle{0.75}}

\put(1.2,9.4){\vector(0,-1){0}}

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

\put(6,5.8){\line(-1,1){3.2}}

\put(6,5.8){\vector(-1,1){1.5}}

\put(4.2,7){\makebox(0,0){$\frac{1}{4}$}}
\end{picture}


$\{1,2\}$ and $\{3,5\}$ are closed sets and constitute subchains
which are ergodic.

The $2\times2$ chain with $P = \left( \begin{array}{cc} 1-p &amp; p
\\ \alpha &amp; 1-\alpha \end{array} \right)$

has equilibrium distribution $\ds \left( \frac{\alpha}{\alpha +
p}, \frac{p}{\alpha + p} \right).$

Mean recurrence times are $\ds \frac{\alpha+p}{\alpha} $ and $\ds
\frac{\alpha + p}{p}$ so in these cases we have $$\mu_1 =
\frac{5}{2} \hspace{.2in} \mu_2 = \frac{5}{3} \hspace{.2in} \mu_3
= \frac{13}{6} \hspace{.2in} \mu_5 = \frac{13}{7}$$

States 4 and 6 intercommunicate and are of the same type.

\begin{eqnarray*} f_{44} &amp; = &amp; \frac{1}{4} \cdot \frac{1}{5} + \frac{1}{4} \cdot
\frac{2}{5} \cdot \frac{1}{5} + \frac{1}{4} \cdot \left(
\frac{2}{5} \right)^2 \cdot \frac{1}{5} + ... \\ &amp;= &amp; \frac{1}{4}
\cdot \frac{1}{5} \left( 1 + \frac{2}{5} + \left( \frac{2}{5}
\right)^2 + ...\right) \\ &amp; = &amp; \frac{1}{12} &lt; 1 \end{eqnarray*}
so 4 and 6 are transient.


\item[(b)] $\ds P(X_n = a| X_n = a_{n-1} , ....) = P(X_n=a|X_{n-1}
= a_{n-1})$

The number of empty boxes after $n$ balls have been thrown depends
only on how many boxes were empty after $(n-1)$ balls had been
thrown, together with the result of the $n$-th throw.

For $k&lt;N$ we have
\begin{eqnarray*} P(X_{n+1} = k)  &amp; = &amp;  P(X_n = k {\rm\ and\ ball\ }(n+1){\rm \ lands\ in\
a}\\  &amp; &amp; \hspace{2in} {\rm non\ empty\ box)}
\\&amp; &amp; + P(X_n = k+1 {\rm\ and\ ball\ }(n+1){\rm\ \ lands\ in\ an\ } \\ &amp; &amp; \hspace{2.2in}{\rm empty\ box})
\\ &amp; = &amp; \left( 1 - \frac{k}{N} \right) P(X_n = k) + \frac{k+1}{N}
P(X_n = k+1) \\ {\rm i.e.\ }p_{n+1} &amp; = &amp; \left( 1 - \frac{k}{N}
\right) p_n(k) + \frac{k+1}{N}p_n(k+1)\end{eqnarray*}


\end{description}



\end{document}
</pre></body></html>