\documentclass[a4paper,12pt]{article} \newcommand{\ds}{\displaystyle} \newcommand{\pl}{\partial} \parindent=0pt \begin{document} {\bf Question} Describe briefly a Markov chain. \begin{description} \item[(a)] A Markov chain $\{X_n\}\ \ n = 0, 1, 2, ...$ has only two states and for $n = 1, 2,\ldots$ $$P(X_n = 1| X_{n-1} = 0) = p$$ $$P(X_n = 0| X_{n-1} = 1) = \alpha$$ Prove that $$P(X_1 = 0 | X_0 = 0, X_2 = 0) = \frac{(1-p)^2}{(1-p)^2 + p\alpha}$$ \item[(b)] A Markov chain with statespace composed of all the non-negative integers has one-step transition probabilities defined for $j = 0, 1, 2,\ldots$ by $$P_{j,j+1} = p,$$ and $$P_{j,0} = 1 - p,$$ where $0 < p < 1.$ Find the probability that, stating from state 0, the system will return to state 0 for the first time at the $n$-th step $(n \geq 1).$ Hence, or otherwise, show that state 0 is positive recurrent. \end{description} \vspace{.25in} {\bf Answer} A Markov chain is a sequence $(X_n)$ of integer - valued random variables with the property that $$P(X_n = k| X_0 = a_0, X_1 = a_1 , ..., X_{n-1} = j) = P(X_n = k|X_{n-1} = j)$$ This is the Markov property. \begin{description} \item[(a)] $\ds P(X_1 = 0| X_0 = 0 \ \&\ X_2 = 0)$ $\ds = \frac{P(X_1=0 \ \&\ X_0=0 \ \&\ X_2 = 0)}{P(X_0 = 0 \ \&\ X_2 = 0)}$ $\ds = \frac{P(X_1=0 \ \&\ X_0=0 \ \&\ X_2 = 0)}{P(X_0=0 \ \&\ X_1=0 \ \&\ X_2 = 0)+ P(X_0=0 \ \&\ X_1=1 \ \&\ X_2 = 0)}$ $\ds = \frac{P(X_2 = 0 | X_1 = 0 \ \&\ X_0 = 0) P(X_1 = 0| X_0 = 0) P(X_0 = 0)}{{\rm Num.}+ P(X_2 = 0 | X_1 = 1 \ \&\ X_0 = 0) P(X_1 = 1| X_0 = 0) P(X_0 = 0)}$ [where Num. = numerator] Using the Markov property and cancelling $P(X_0 = 0)$ this reduces to $$\frac{(1-p)^2}{(1-p)^2 + p \alpha}$$ \item[(b)] To arrive at state 0 for the first time at step $n,$ the Markov chain must follow the path $$0 \to 1 \to 2 \to ... \to n-1 \to 0$$ and so the required probability is $\ds p^{n-1}(1-p)$. The probability of eventual return is $$\sum_{n=1}^\infty p^{n-1}(1-p) = 1 \hspace{.5in} (0 < p < 1)$$ The mean recurrence time is (1-p)\sum_{n=1}^{\infty}np^{n-1}=\frac{1}{1-p}<\infty\ \ {\rm for}\ 0