\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

A Markov chain consists of a simple random walk taking place on a
circle. The states consist of equally spaced points labelled $0,\
1,\ 2,\ \cdots,\ a-1$ in a clockwise direction. At each step of
the random walk transition takes place as follows:

\begin{description}
\item[(i)]
a clockwise step with probability $p$,

\item[(ii)]
an anticlockwise step with probability $q$,

\item[(iii)]
no change of position with probability $1-p-q$,
\end{description}

where $pq \ne 0$, and $p+q<1$.

${}$

Write down the transition matrix of the Markov chain.

${}$

Explain how the classification theorems enable you to deduce that
in this case there is a long term equilibrium state occupancy
distribution. Find this distribution. Find the mean recurrence
time for any positive recurrent states.



\vspace{.25in}

{\bf Answer}

PICTURE

The transition matrix is as follows

$$\bordermatrix{& 0 & 1 & 2 &  & & & a-1 \cr 0 & 1-p-q & p & 0 &
\cdots &  & 0 & q \cr 1 & q & 1-p-q & p & &  & & 0 \cr 2&0 & q &
1-p-q & p &   & & 0\cr \vdots & \vdots & & & & & &  \vdots \cr & 0
& & & &   q & 1-p-q & p \cr a-1 & p & 0 & \cdots & &  0 & q &
1-p-q }$$

Now all the states intercommunicate, so they are of the same type
(positive recurrent).  Since $1-p-q \not= 0$  the states are all
aperiodic.  Thus we have a finite irreducible aperiodic
distinction, which is also the equilibrium distribution.

Let {\boldmath$\pi$}$= (\pi_0, \pi_1, ..., \pi_{a-1})$ denote the
stationary distribution.  If it satisfies {\boldmath$\pi$} =
{\boldmath$\pi$}P.  Thus we have \begin{eqnarray*} \pi+0 & = &
(1-p-q)\pi_0 + q\pi_1 + p\pi_{a-1} \\ \pi_k & = & p\pi_{k-1} +
(1-p-q)\pi_k + q\pi_{k+1} \\ \pi_{a-1}& = & q\pi_0 + p\pi_{a-2} -
(1-p-q)\pi_{a-1} \end{eqnarray*}

Note Columns sum to 1.  Therefore (1,1,...,1) is a fixed vector
and therefore {\boldmath$\pi$}$\ds= \left(\frac{1}{a},
\frac{1}{a}, ..., \frac{1}{a}\right)$

\begin{eqnarray} p\pi_{a-1} + q\pi_1 - (p+q)\pi_0 & = & 0 \\
q\pi_{k+1}-(p+q)\pi_k+p\pi_{k-1} & = & 0 \\ q\pi_0 + p\pi_{a-2} -
(p-q)\pi_{a-1} & = & 0 \end{eqnarray}

Solving  (2) gives$$\pi_k = A + b\left(\frac{p}{q}\right)^k
\hspace{.5in} if\, p\not=q $$ $$\pi_k = A + B k \hspace{.5in} if\,
p=q$$

{\underline{Case 1}} $p\not= q$.  From (1) we have
\begin{eqnarray}p\left(A + B\left(\frac{p}{q}\right)^{a-1}\right)
+ q\left(A+B\left(\frac{p}{q} \right)\right) \nonumber \\ -
(p+q)\left(A + B\left( \frac{p}{q}\right)^{a-1} \right) & = & 0
\nonumber \\ {\rm i.e.\ \ }B \left[ p
\left(\frac{p}{q}\right)^{a-1} - q \right] & = & 0
\end{eqnarray} So either B = 0 or  $\ds \left[ p
\left(\frac{p}{q}\right)^{a-1} - q \right]  = 0.$

From (3)
\begin{eqnarray} q(a+b) + p\left(A +b\left(\frac{p}{q} \right)
^{a-2} \right)  - (p+q) \left( a + b\left(\frac{p}{q} \right)
^{a-1} \right) & = & 0 \nonumber \\ B \left(\left\{p \left(
\left(\frac{p}{q}\right)^{a-2} - \left(\frac{p}{q}
\right)^{a-1}\right) \right\} - \left[p \left(\frac{p}{q}
\right)^{a-1}-q \right]\right) & = & 0 \end{eqnarray}

From (4) if [ ] =0 , since $\{ \} \not= 0$ in (5), we deduce B=0.

Thus $B=0$ and $\ds \pi_k = A$

{\underline {Case 2}} $p=q$

From(1) we have $$P(A + B(a-1)) + q(A+B) - (p+q)A = 0$$ i.e. $\ds
B[p(a-1)+q]=0$.  Now { }  $>$ 0 so B=0 and again $\pi_k=A$.

Now $\ds \sum_{k=0}^{a-1} \pi_k = 1$ so $\ds A = \frac{1}{a}$ and
so
{\boldmath$\pi$}=$\ds\left(\frac{1}{a},\frac{1}{a},...,\frac{1}{a}\right)$

The mean recurrence times are the reciprocals  of the equilibrium
probabilities.  i.e. all equal to a.


\end{document}