\input macros
%%
\line {\bf IB/IIA --- Michaelmas 2000\hfil GRG}
\bigb
\cl {\bf MARKOV CHAINS}
\med
\cl {\bf Remarks on Example Sheet 3}
\bigb

\no{3.1} First,
$$
\P(\min\{S,T\}>z) = \P(S>z)\P(T>z)=e^{-\a z}e^{-\b z}= e^{-(\a+\b)z}.
$$
By integration, $P(S<T)={\a}/{(\a+\b)}$. 
Then 
$$
\P(S<T,\ \min\{S,T\}\ge t )= 
 \P(t\le S < T )= \frac{\a}{\a+\b}e^{-(\a+\b) t}
$$ 
by integration.
Students should be encouraged to think what these results mean, 
e.g., in terms of
arrivals of rates $\a$ and $\b$ respectively. Also, more general
results of this kind are obviously important when describing 
continuous time chains 
by specifying rates
for individual transitions.

\no{3.2}
Compute $\E (e^{\t T}\mid N=n)$ and then $\E (e^{\t T})$.

\no{3.3}
Let $F$ and $W$ be the incoming Poisson processes,
and let $N(t)= F(t)+W(t)$. Certainly $N(0)=0$ and $N$
is non-decreasing. Arrivals of flies during $[0,s]$
are independent of arrivals during $(s,t]$, if
$s<t$;	similarly for wasps. Therefore	the aggregated
arrival process during $[0,s]$ is independent of the
aggregated process during $(s,t]$. Now
$$\P\bigl(N(t+h)=n+1\mid N(t)=n\bigr) =\P(A\bigtriangleup B)$$
where
$$\align 
A&=\{\T{one fly arrives during }(t,t+h]\},\\
B&=\{\T{one wasp arrives during }(t,t+h]\}.
\endalign $$
We have that
$$\align
\P(A\bigtriangleup B)&=\P(A)+\P(B)-\P(A\cap B)\\
&=\lambda h+\mu h-(\lambda h)(\mu h)+o(h)
=(\lambda +\mu) h+o(h).
\endalign$$
Finally
$$\P\bigl(N(t+h)>n+1\mid N(t)=n\bigr)\le \P(A\cap B)+\P(C\cup D),$$
where
$C=\{$two or more flies arrive in $(t,t+h]\}$ and
$D=\{$two or more wasps arrive in $(t,t+h]\}$.
This probability is no greater than
$(\lambda h)(\mu h)+o(h)=o(h)$.

\no{3.4} Let $I$ be the incoming Poisson process, and let $G$
be the process of arrivals of green insects. Matters of independence are
dealt with as above. Finally
$$\align
\P\bigl(G(t+h)=n+1\mid G(t)=n\bigr)&=p\P\bigl(I(t+h)=n+1\mid I(t)=n\bigr)+o(h)\\
&=p\lambda h+o(h),
\endalign$$
and
$$
\P\bigl(G(t+h)>n+1\mid G(t)=n\bigr)
\le \P\bigl(I(t+h)>n+1\mid I(t)=n\bigr)
=o(h).$$

\no{3.5} Conditioning on $T_1$ and using the time-homogeneity
of the process,
$$\P\bigl(E(t)>x\mid T_1=u\bigr)=
\cases \P\bigl(E(t-u)>x\bigr)&\T{if }u\le t\\
0&\T{if }t<u\le t+x\\ 1&\T{if }u>t+x
\endcases$$
(draw a diagram to help you see this).
Therefore
$$\align
\P\bigl(E(t)>x\bigr)&=
    \int^{\oo}_0\P\bigl(E(t)>x\mid T_1=u\bigr)\lambda e^{-\lambda u}\,du\\
&=\int^t_0\P\bigl(E(t-u)>x\bigr)\lambda e^{-\lambda u}\,du+\int^{\oo}_{t+x}
\lambda e^{-\lambda u}\,du.
\endalign$$

You may solve the integral equation using Laplace transforms.
Alternately you may guess the answer and then check that
it works. The answer is
$\P\bigl(E(t)\le x\bigr)=1-e^{-\lambda x}$,
the exponential distribution. Actually this answer is
obvious since $E(t)>x$ if and only if there is no arrival
in $[t,t+x]$, an event having probability $e^{-\lambda x}$.


\no{3.6} The forward equations are
$$p'_n(t)=\lambda_{n-1}p_{n-1}(t)-\lambda_np_n(t),\qq n\ge 0,$$
where $\lambda_i=i\lambda+\nu$. The process is honest, and therefore
$m(t)=\sum_n np_n(t)$
satisfies
$$\align
m'(t)&=\sum^{\oo}_{n=1}n\bigl[(n-1)\lambda +\nu\bigr]p_{n-1}(t)-\sum^{\oo}_{n=0}
n(n\lambda +\nu)p_n(t)\\
&=\sum^{\oo}_{n=0}\bigl\{\lambda[(n+1)n-n^2]+\nu[(n+1)-n]\bigr\}p_n(t)\\
&=\sum^{\oo}_{n=0}(\lambda n+\nu)p_n(t)=\lambda m(t)+\nu.
\endalign$$
Solve subject to $m(0)=0$ to obtain
$m(t)= \nu(e^{\lambda t}-1)/\lambda$.

\no{3.7}
By standard properties of the Poisson process the answers are:
{\rm (a)} $e^{-8} 8^3/3!$, {\rm (b)} $7^3/8^4$, {\rm (c)} $e^{-2}$.

\no{3.8}
Let $T$ be the time to cross and $J$ the time at which the
first car passes. Then
$$\eqalign{
\E (T)&=a\P (J>a)+\int_0^a (s+\E (T))\lambda e^{-\lambda s} ds\cr
&=(1-e^{-\lambda a})\left(\E (T)+{1\over\lambda}\right)\; .\cr}$$
Hence $\E (T)$. Check that it is correct as $\lambda\to 0$. Walking straight
across replaces $a$ by $2a$ and $\lambda$ by $2\lambda$, because the 
sum of two
independent Poisson processes of rate $\lambda$ is a Poisson process
of rate $2\lambda$. Using an island, it takes twice as long on average
as a single lane. How much quicker is it to use an island?

\no{3.9}
For $0\leq s\leq t$, the conditional distribution of $X_t$,
given the first split $J$ occurs at $s$, is the same as the
distribution of $X_{t-s}+\widetilde X_{t-s}$, where $\widetilde X$ is an
independent copy of $X$. So
$$\E (z^{X_t}\mid J=s)=\cases
\E (z^{X_{t-s}+\widetilde X_{t-s}})&\text{for } 0\leq s\leq t,\\
z&\text{for }s\geq t,\endcases
$$
and
$$\eqalign{
\phi (t)&=\int_0^\infty\lambda e^{-\lambda s}\E (z^{X_t}\mid J=s)ds\cr
&=ze^{-\lambda t}+\int_0^t\lambda e^{-\lambda s}\phi (t-s)^2ds\, .\cr}$$
Put $u=t-s$, multiply by $e^{\lambda t}$ and differentiate to see
that $d\phi /dt =\lambda\phi (\phi-1 )$, and so $\phi=
z(1-q)/(1-zq)$ as required.

\no{3.10}
(a) There are many ways of calculating $ G^n$; let us use
difference equations. Note first that $ G^0= I$, the
identity matrix. Write
$$G^n=\pmatrix a_n&b_n\\
c_n&d_n\endpmatrix,\qq n\ge 0,$$
and use the equation $G^{n+1}= G\cdot  G^n$ to find that
$$
a_{n+1}=-\mu a_n+\mu c_n,\q
c_{n+1}=\lambda a_n-\lambda c_n.
$$
Hence $a_{n+1}=-(\mu/\lambda)c_{n+1}$ for $n\ge 0$, and the first
difference equation becomes
$a_{n+1}=-(\lambda+\mu)a_n$, $n\ge 1$,
which, subject to $a_1=-\mu$, has solution
$a_n= (-1)^n\mu(\lambda+\mu)^{n-1}$, $n\ge 1$.
Therefore $c_n=(-1)^{n+1}\lambda(\lambda+\mu)^{n-1}$ for $n\ge 1$, and
one may see similarly that $b_n=-a_n$, $d_n=-c_n$ for
$n\ge 1$. Using the facts that $a_0=d_0=1$ and $b_0=c_0=0$,
we deduce that
$$
\sum^{\oo}_{n=0} \frac{t^n}{n!}\, G^n= P_t
= \frac1{\lambda+\mu}\pmatrix\lambda+\mu e^{-(\lambda+\mu)t}
&\mu-\mu e^{-(\lambda+\mu)t}\\
\lambda-\lambda e^{-(\lambda +\mu)t}&\mu+\lambda e^{-(\lambda+\mu)t}
\endpmatrix.
$$
\flushpar
(b) With $\boldsymbol\pi=(\pi_1,\pi_2)$, we have that
$$
-\mu\pi_1+\lambda\pi_2=0,\q
\mu\pi_1-\lambda\pi_2=0,
$$
and therefore $\pi_1=(\lambda/\mu)\pi_2$. In addition, $\pi_1+\pi_2=1$ if
$\pi_1={\lambda}/(\lambda+\mu) = 1 - \pi_2$.

\no{3.11}
Assume that $\lambda\geq\mu$, then
$$\P_0\hbox{(hit $i$)} =\cases
1&\text{if } i\geq 0\\
(\mu /\lambda )^{-i}&\text{if } i<0.
\endcases
$$
Hence the return probability for any state is $2\mu$. On each visit,
$(X_t)_{t\geq 0}$ spends an average time $1/q_i$ in state $i$. Hence
$$
\E_0\Bigl(\hbox{total time in state $i$}\Bigr)=\cases
\dfrac1{(\lambda -\mu )q_i}&\text{if } i\geq 0\\
\dfrac{(\mu /\lambda )^{-i}}{(\lambda -\mu )q_i}&\text{if } i<0.
\endcases
$$

If $\mu =0$, then $(X_t)_{t\geq 0}$ is explosive if and only if
$\sum_{i=1}^\infty 1/q_i<\infty$. 

If $\mu\in [0,\half )$ then
certainly the jump chain $Y_n\to\infty$ as $n\to\infty$ so
$(X_t)_{t\geq 0}$ cannot explode to $-\infty$, but comparison with the
case $\mu =0$ shows that if $\sum_{i=1}^\infty 1/q_i=\infty$ then
$(X_t)_{t\geq 0}$ cannot explode to $\infty$ either. To see that this
condition is also necessary for non-explosion when $\mu\in [0,\half
)$, observe that $(X_t)_{t\geq 0}$ makes only finitely many visits to
states $i\leq 0$ and
$$
\E_0\Bigl(\hbox{total time to the right of the origin}\Bigr)
=\sum_{i=1}^\infty
\frac1{(\lambda -\mu )q_i}.
$$
Finally, in the case $\lambda =\mu$, $(Y_n)_{n\geq 0}$ is recurrent so
$(X_t)_{t\geq 0}$ does not explode.


\bye

