\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} & \frac{1}{2} & 0 & 0 & 0 &0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{8}& 0 & \frac{7}{8} & 0\\ \frac{1}{4} & \frac{1}{4} & 0 & 0 & \frac{1}{4} & \frac{1}{4} \\ 0 & 0 & \frac{3}{4} & 0 & \frac{1}{4} & 0 \\ 0 & \frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & \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} & \frac{1}{2} & 0 & 0 & 0 &0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{8}& 0 & \frac{7}{8} & 0\\ \frac{1}{4} & \frac{1}{4} & 0 & 0 & \frac{1}{4} & \frac{1}{4} \\ 0 & 0 & \frac{3}{4} & 0 & \frac{1}{4} & 0 \\ 0 & \frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & \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 & p \\ \alpha & 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} & = & \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} + ... \\ &= & \frac{1}{4} \cdot \frac{1}{5} \left( 1 + \frac{2}{5} + \left( \frac{2}{5} \right)^2 + ...\right) \\ & = & \frac{1}{12} < 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