\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<p<1.$$



So the state 0 is positive recurrent.

\end{description}



\end{document}