\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 3}
\bigb

\no {3.1} Suppose that $S$ and $T$ are independent exponentially-distributed 
random variables with
parameters $\a$ and $\b$ respectively. What is the distribution of
$\min\{ S,T\}$? What is the probability that $S\leq T$? Show that the two
events $\{S<T\}$ and $\{\min \{S,T\} \ge t\}$ are independent.

\no {3.2} Let $T_1,T_2,\ldots$ be independent exponentially-distributed
random
variables with parameter $\lambda$ and let $N$ be an independent
geometric random variable with
$$\P (N=n)=\b (1-\b)^{n-1},\qq n=1,2,\ldots.$$
Show that $T=\sum_{i=1}^N T_i$ has an exponential distribution with
parameter $\lambda\b$.

\no{3.3}
{\bf Superposition.}  Flies and wasps land on your dinner plate in the
manner of independent Poisson processes with respective intensities  $\lambda $
and  $\mu $.  Show that the arrivals of flying objects form a Poisson process 
with intensity	$\lambda  + \mu $.


\no{3.4}{\bf Thinning.}	Insects land in the soup in the manner of a Poisson
process with intensity  $\lambda $,  and each such insect is green with 
probability  $p$,  independently of the colours of all other insects.  Show 
that the arrivals of green insects form a Poisson process with intensity  
$\lambda p$.


\no{3.5}Let  $T_n$  be the time of the  $n$th  arrival in a Poisson process  $N$
with intensity	$\lambda $,  and define the excess lifetime process
$E(t) = T_{N(t) + 1} - t$,
being the time one must wait subsequent to  $t$  before the next arrival.  Show
by conditioning on  $T_1$  that
$$
\P \bigl(E(t) > x\bigr) = e^{-\lambda(t+ x)} +
\int ^t_0 \P \bigl(E(t-u) > x\bigr)\lambda e^{-\lambda u}\,du.
$$
Solve this integral equation in order to find the distribution function of  
$E(t)$.  Explain your conclusion.
[If necessary, you may assume that
there is a unique eligible solution to the integral equation, 
but it is worth trying
to do the problem without making this assumption.]  



\no{3.6}Let  $B$  be a process of simple birth with immigration  with
parameters $\lambda$ and $\nu$, and with  $B(0) =
0$; the corresponding birth rates are $\lambda_n = n\lambda + \nu$.  
Write down the sequence of differential-difference equations for  $p_n(t) 
= \P (B(t) = n)$.  Without solving these equations, use them to show that
$m(t) = \E B(t)$  satisfies
$m'(t) = \lambda m(t) + \nu$,
and solve for  $m(t)$.

\no {3.7} Arrivals of the Number 1 bus form a Poisson process with
rate 1 bus per hour, and arrivals of the Number 7 bus form an
independent Poisson process of rate 7 buses per hour.
\ii{(a)} What is the probability that exactly 3 buses pass by in 1
hour?
\ii{(b)} What is the probability that exactly 3 Number 7 buses pass by
while I am waiting for a Number 1?
\ii{(c)} When the maintenance depot goes on strike half the buses break
down before they reach my stop. What then is the probability that I
wait for 30 minutes without seeing a single bus?

\no {3.8} A pedestrian wishes to cross a single lane of fast-moving
traffic. Suppose the number of vehicles that have passed by time $t$
constitutes a Poisson process with rate $\lambda$, and suppose it takes 
a fixed time $a$
to walk across the lane. Assuming the pedestrian can foresee correctly
the times at which vehicles will pass by, how long on average does it
take to cross over safely? [{\it Hint\/}: Consider the time at which the first
car passes.]

How long on average does it take to cross two similar lanes 
\ii{(a)} when
one must walk straight across (assuming that the pedestrian will not cross
if at any time whilst crossing a car passes in either direction),  and
\ii{(b)} when an island in the middle of the
road makes it safe to stop half-way?

\no {3.9} Each bacterium in a colony splits into two identical
bacteria after a time having the  exponential distribution
with parameter $\lambda$; these bacteria then
split in the same way but independently. Let $X_t$ denote the size of
the colony at time $t$, and suppose $X_0=1$. Show that the probability
generating function $\phi (t)=\E (z^{X_t})$ satisfies
$$
\phi (t)=ze^{-\lambda t}+\int_0^t\lambda e^{-\lambda s}\phi
(t-s)^2ds.
$$ 
Change variables $u=t-s$ in the integral and deduce that
$d\phi / dt = \lambda \phi (\phi-1)$. 

[{\it Hint\/}: You may need to use the
fact, which you should check, that ${d\over{dt}} \int_0^t f(s,t)ds
=f(t,t)+ \int_0^t {\partial  \over {\partial t}} f(s,t) ds$.] 

Hence deduce that, for $q=1-e^{-\lambda t}$, and $n=1,2,\ldots$,
$$\P (X_t=n)=q^{n-1}(1-q).$$

\comment
\no{3.10} Compute $p_{11}(t)$ for for a continuous-time Markov chain with
generator
$$
G=\pmatrix -2&1&1\\ 4&-4&0\\ 2&1&-3
\endpmatrix
$$
\endcomment

\no{3.10}Let  $X$  be a Markov chain on  $\{1,2\}$  with generator
$$
 G = \pmatrix
-\mu &\mu\\
\lambda &-\lambda
\endpmatrix $$
where  $\lambda \mu  > 0$.
\ii{(a)} Calculate  $ G^n$  and hence find
$\sum_{n=0}^\oo ({t^n}/{n!})  G^n$.
\ii{(b)} Solve the equation  $\boldsymbol\pi  G = \bold 0$  in order to find the stationary
distribution.  Verify that  $p_{ij}(t) \rightarrow  \pi _j$  as  $t 
\rightarrow  \infty $.

\no {3.11\rlap{*}} Let $(X_t)_{t\geq 0}$ be a Markov chain on the integers
with transition rates $q_{i,i+1}=\lambda q_i$, $q_{i,i-1}=\mu q_i$, and
$q_{i,j}=0$ if $|j-i|\geq 2$, where $\lambda +\mu =1$ and $\lambda,
\mu, q_i>0$ for all
$i$. Find, for all $i$,
\ii{(a)} the probability, starting from 0, that $X_t$ ever hits $i$;
\ii{(b)} the expected total time spent in state $i$, starting from 0.

In the case $\mu =0$, write down a necessary and sufficient condition
for $(X_t)_{t\geq 0}$ to be explosive. Why is this condition necessary
for $(X_t)_{t\geq 0}$ to be explosive for all $\mu\in [0,\half )$?

Show that, in general, $(X_t)_{t\geq 0}$ is non-explosive if and only
if one of the following conditions holds:
\ii{(i)} $\lambda =\mu$,
\ii{(ii)} $\lambda >\mu$ and $\sum_{i=1}^\infty 1/q_i=\infty$,
\ii{(iii)} $\lambda <\mu$ and $\sum_{i=-\infty}^{-1} 1/q_i=\infty$.

\bye
