\magnification=1100
\input probmacros
\parindent=10pt
%%
\line {\bf IB/IIA --- Michaelmas 2000\hfil GRG}
\line{\hfil \tt g.r.grimmett{\@}statslab.cam.ac.uk}
\line{\hfil\tt http://www.statslab.cam.ac.uk/$\sim$grg/}
\bigb
\cl {\bf MARKOV CHAINS}
\med
\cl {\bf Example Sheet 4}
\bigb
\no {4.1} Two fleas are bound together to take part in a nine-legged
race on the vertices $A,B,C$ of a triangle. Flea 1 hops at random
times in the clockwise direction; each hop takes the pair from one
vertex to the next and the times between successive hops of Flea 1 are
independent random variables, each with with exponential distribution,
mean $1/\lambda$. Flea 2 behaves similarly, but hops in the
anti-clockwise direction, the times between his hops having mean
$1/\mu$. Show that the probability that they are at $A$ at a given
time $t>0$ (starting from $A$ at time $t=0$) is
$${1\over 3} + {2\over 3}\,\exp\left\{ -
{3(\lambda +\mu )t\over 2}\right\}\cos
\left\{ {\sqrt 3(\lambda -\mu )t\over 2}\right\}.
$$

\no{4.2} Let $(X_t)_{t\geq 0}$ be a birth-death process with
rates $\lambda_n=n\lambda$ and $\mu_n=n\mu$, and suppose $X_0=1$. Show
that $h(t)=\P (X_t=0)$ satisfies
$$h(t)=\int_0^t e^{-(\lambda +\mu )s}\{\mu +\lambda h(t-s)^2\} ds$$
and deduce that if $\lambda\ne\mu$ then
$$
h(t)=\frac{\mu e^{\mu t}-\mu e^{\lambda t}}{\mu e^{\mu t}-\lambda
e^{\lambda t}}.
$$

\no{4.3} Consider an immigration-death process  $X$, being a birth-death
process with birth rates
$\lambda_n = \lambda$ and death rates $\mu_n = n\mu$; let  $Y$	be the
jump chain.
Find the transition matrix of  $Y$,  and show that
it has as stationary distribution
$$
\pi _n = 
\frac1{2(n!)} \ga( 1+\frac n\rho\dr)\rho^n e^{-\rho}
$$
where $\rho = \lambda/\mu$. Explain why this differs from the stationary
distribution of $X$.

\no{4.4} Let $(X_t)_{t\geq 0}$ be an irreducible Markov chain with
generator $G$. Show that the transition probabilities of
$(X_t)_{t\geq 0}$ and its jump chain are related by
$$
\int_0^\infty p_{i,i} (t)dt = {1\over g_i}\,\sum_{n=0}^\infty\pi_{i,i}(n)
$$
and deduce that $(X_t)_{t\geq 0}$ is transient if and only if, for
some state $i$,
$$\int_0^\infty p_{i,i}(t)dt <\infty .$$

\no{4.5}  Customers arrive at a certain queue in a Poisson process with
rate $\lambda$. The single `server' has two states $A$ and $B$, state
$A$ signifying that he is `in attendance' and state $B$ that he is
having a tea-break. Independently of how many customers are in the
queue, he fluctuates between these states as a Markov chain $Y$ on
$\{A,B\}$ with generator
$$
\pmatrix-\a&\a\\
\b&-\b
\endpmatrix.
$$
The total service time of any customer is exponentially distributed
with parameter $\mu$ and is independent of the chain $Y$ and of the
service times of other customers.

Describe the system as a Markov chain $X$ with state-space
$$\{ A_0,A_1,A_2,\ldots\}\cup\{ B_0,B_1,B_2,\ldots\}\, ,$$
$A_n$ signifying that the server is in state $A$ and there are $n$
people in the queue (including anyone being served) and $B_n$
signifying that the server is in state $B$ and there are $n$ people in
the queue.

Give a very brief explanation why, for some $\t$ in $(0,1]$, and
$k=0,1,2,\ldots$,
$$P\hbox{($X$ hits $A_0$}\mid X_0=A_k)=\t^k .$$
Show that $(\t -1)f(\t )=0$, where
$$f(\t )=\lambda^2\t^2-\lambda (\lambda +\mu +\a +\b )\t +(\lambda +\b
)\mu .$$

By considering $f(1)$ or otherwise, prove that $X$ is transient if
$\mu\b <\lambda (\a +\b )$, and explain why this is intuitively
obvious.

\no{4.6} Consider the continuous-time birth-death chain
$(X_t)$ with non-zero birth rates $\lambda_i$, $i\geq 0$, and death rates
$\mu_i$, $i\geq 1$. Suppose
$${\mu_i\over\lambda_i} =\left({i\over i+1}\right)^\a\, ,\q\mu_i=i^\b\,
,\q i\geq 1 ,$$
with $\a ,\b\in\R$ and $\lambda _0=1$. Determine for which values of
$\a$ and $\b$ the chain is transient, for which values it is null
recurrent, and for which positive recurrent.

\no{4.7} In each of the following cases, compute
$\lim_{t\to\infty}\P (X_t=2\mid X_0=1)$ for the Markov chain $(X_t)_{t\geq
0}$ with the given generator on $\{ 1,2,3,4\}$:

\ii{(a)}\q $\displaystyle{\pmatrix
-2&1&1&0\\ 0&-1&1&0\\ 0&0&-1&1\\ 1&0&0&-1
\endpmatrix ,}$
\hskip.5truein
(b)\q $\displaystyle{\pmatrix
-2&1&1&0\\ 0&-1&1&0\\ 0&0&-1&1\\ 0&0&0&0\endpmatrix ,}$
\bigb
\ii{(c)}\q $\displaystyle{\pmatrix
-1&1&0&0\\ 1&-1&0&0\\ 0&0&-2&2\\ 0&0&2&-2\endpmatrix ,}$
\hskip.5truein
(d)\q $\displaystyle{\pmatrix
-2&1&0&1\\ 0&-2&2&0\\ 0&1&-1&0\\ 0&0&0&0\endpmatrix .}$

\no{4.8} Customers arrive at a single-server queue in a Poisson stream
of rate $\lambda$. Each customer has a service requirement distributed
as the sum of two independent exponential random variables of parameter
$\mu$. Service requirements are independent of one another and of the arrival
process.

Write down the generator $G$ of a continuous-time Markov chain which models
this, explaining very briefly what the states of the chain represent. Calculate
the essentially unique invariant measure for $G$, and deduce that the chain
is positive recurrent if and only if ${\lambda/\mu} < \half$.

\no{4.9\rlap{*}} Calls arrive at a telephone exchange as a Poisson process
of rate $\lambda$, and the lengths of calls are independent
exponentially-distributed random variables with parameter $\mu$. Assuming that
infinitely many telephone lines are available, set up a Markov chain
model for this process.

Show that for large $t$ the distribution of the number of lines in use
at time $t$ is approximately Poisson with mean $\lambda /\mu$.

Find the mean length of the busy periods during which at least one
line is in use.

Show that the expected number of lines in use at time $t$, given that
$n$ are in use at time 0, is $ne^{-\mu t}+\lambda (1-e^{-\mu t})/\mu$.

Show that, in equilibrium, the number $N_t$ of calls finishing in the
time interval $[0,t]$ has Poisson distribution of mean $\lambda t$.

Is $(N_t)_{t\geq 0}$ a Poisson process?

\medskip
\hrule
\medskip
\flushpar
{\bf Paper IV type questions: IIA only}

Note that it is not necessarily the case that the Paper IV question will be
a straight essay; as with other courses, there may be a slightly harder and/or
longer problem to solve, or the question may mix an essay component and a
problem component. The following give examples of the sort of essays that
might arise. You should discuss essay writing with your supervisor --- there
is more to it than just regurgitating bits of your notes.

\no{IV.1}  Write an essay on the relation between discrete-time and
continuous-time Markov chains. [{\it The mark scheme for this question indicates
that candidates could have obtained marks by mentioning: 
Behaviour of the jump chain;
Properties inherited from the jump chain; Derivation of backward equation from
the jump chain; Invariant measures, positive recurrence; 
Discrete chain obtained by regular sampling of a continuous chain, 
convergence to equilibrium.}]

\no{IV.2} Write an essay on transience and recurrence in discrete-time Markov
chains.

\no{IV.3} Write an essay on the Poisson process, including a discussion of the
equivalence of the holding times, infinitesimal and transition
probability definitions. 

\no{IV.4} Write an essay on the long-time behaviour of 
discrete-time Markov chains.








\bye
