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

\no{4.1}The position evolves as a Markov chain with generator
$$G=\pmatrix
-\lambda -\mu&\lambda&\mu\cr\mu&-\lambda
-\mu&\lambda\cr\lambda&\mu&-\lambda -\mu
\endpmatrix
$$
and the problem is to compute $p_{1,1}(t)$. Find the eigenvalues,
and follow the method of Problem 3.10.
Convergence to equilibrium gives $p_{1,1}(\infty
)=\frac13$, which is useful in fixing the constants.

\no{4.2} Condition on the time of the first event as in Problem 3.9
and use $\P (X_t=0\mid X_s=2)=h(t-s)^2$.

\no{4.3} The transition matrix $\bold Q=(q_{i,j})$ of $Y$
is given by
$$q_{i,j}=\cases\dfrac{i\mu}{\lambda+i\mu}&\T{if }j=i-1\\
\dfrac{\lambda}{\lambda+i\mu}
&\T{if }j=i+1.
\endcases$$
To find the stationary distribution of $Y$, either solve the
equation $\boldsymbol\pi=\boldsymbol\pi\bold Q$, or look for a solution of the
detailed balance equations $\pi_iq_{i,i+1}=\pi_{i+1}q_{i+1,i}$.
Following the latter route, we have that
$$\pi_i=\pi_0\frac{q_{01}q_{12}\cdots q_{i-1,i}}{q_{i,i-1}\cdots q_{21}q_{10}},
\qq i\ge 1,
$$
whence
$\pi_i= {\pi_0} \rho^i(1+i/\rho)/i!$ for $i\ge 1$.
Choosing $\pi_0$ accordingly, we obtain the result.

It is a standard calculation that $X$ has stationary distribution
$\boldsymbol\nu$ given by
$\nu_i= \rho^i e^{-\rho}/i!$ for $i\ge 0$.
The difference between $\boldsymbol\pi$ and $\boldsymbol\nu$ arises
from the fact that the holding-times of $X$ have distributions
which depend on the current state.


\no{4.4} Compute the integral by
$$
\align
\int_0^\infty p_{i,i}(t)dt &=\int_0^\infty\E_i(1_{X_t=i})dt
=\E_i\int_0^\infty 1_{X_t=i}dt\\
&=\E_i\sum_{n=0}^\infty
S_{n+1}1_{Y_n=i}=\sum_{n=0}^\infty\E_i(S_{n+1}\mid Y_n=i)\P_i(Y_n=i)
=\sum_{n=0}^\infty {1\over q_i}\,\pi_{ii}(n) ,
\endalign
$$
where $S_n$ is the $n$th holding time and $(Y_n)_{n\geq 0}$ the
jump chain.

\no{4.5} The generator is given by
$g_{A_i,A_{i+1}}=g_{B_i,B_{i+1}}=\lambda$, $g_{A_i,A_{i-1}}=\mu$,
$g_{A_i,B_i}=\a$, $g_{B_i,A_i}=\b$. In order to reach $A_0$ from $A_k$
you must pass through $A_{k-1},\ldots ,A_1$ and the formula results
from the strong Markov property applied at the times you first hit
these states. By considering the jump chain, $\t =\P_{A_1}(\hbox{hit
$A_0$)}$ and $\mu =\P_{B_1}(\hbox{hit $A_1$)}$ satisfy
$$
(\a +\mu +\lambda )\t =\mu +\lambda\t^2+\a\eta\t ,\q
(\lambda +\b )\eta =\b +\lambda\eta\t. 
$$
Hence $(\t -1)f(\t )=0$. By general results $\t$ is the smallest
non-negative root of
$(\t -1)f(\t )$, so you have to work out whether
$f(\t )$ has a root in $(0,1)$.

\no{4.6} Recurrence is decided by finding $h_i=\P_i(\hbox{hit 0})$ as the
minimal non-negative solution to
$$(\lambda_i+\mu_i)h_i=\mu_ih_{i-1}+\lambda_ih_{i+1},\q h_0=1.$$
Divergence of $\sum i^{-\a}$ is necessary and sufficient.

Positive recurrence is then decided by seeing whether invariant
measures have finite mass, which they do provided $\a -\b <-1$.
Students should be asked what they think is happening when $\a -\b <-1$
and $\a >1$.

\no{4.7} The theorem on convergence to equilibrium given in lectures
applies to irreducible, positive recurrent chains, which {\rm (b)},
{\rm (c)} and {\rm (d)} are not. In {\rm (a)} the invariant
distribution is $(\sixth ,\sixth ,\third ,\third )$ and the theorem
applies to give $\sixth$. In {\rm (b)} state 2 is transient, so the
answer is $0$. In {\rm (c)} any distribution of the form $(\half p,\half
p,\half (1-p) ,\half (1-p))$ is invariant, but the answer is $\half$.
In {\rm (d)} the chain enters the closed class $\{ 2,3\}$ with
probability $\half$; the invariant distribution on $\{ 2,3\}$ is $(\third
,\twothirds )$, so the answer is $\sixth$.

\no{4.8} Let $n$ be the number of service times needed to clear the queue in the
absence of any arrivals. $g_{i,i+2}=\lambda$; $g_{i, i-1}=\mu$. An
invariant measure satisfies $\pi G = 0$, so
$$ \lambda \pi_0 = \mu \pi_1 ; \qquad (\lambda+\mu)\pi_1=\mu \pi_2;
\qquad \mu \pi_{i+1} - (\lambda+\mu)\pi_i + \lambda \pi_{i-2} = 0 \qquad
i\ge 2 .$$
Put $x=\lambda/\mu$ and take $\pi_0=1$. Then $\pi_1=x$, $\pi_2=x(x+1)$, and
the roots of the equation coming from the recurrence are $1$ and
$\a, \b = \half [x \pm \sqrt{x^2 + 4x}]$. For the case $x\ne \half$ write
$\pi_i=A \a^i + B \b^i + C$. The initial values can be used to show that
$C=0$, and $|\a|, |\b| < 1$ for $x < \half$. And so on. 

\no{4.9} The generator is given by $g_i=\lambda +i\mu$,
$g_{i,i+1}=\lambda$ and $g_{i,i+1}=i\mu$, and has invariant distribution
$$
\pi_i=\frac{e^{-\nu}\nu^i}{i!},\q\nu =\lambda /\mu .
$$
To apply the standard result that $p_{i,j}(t)\to\pi_j$ as $t\to\infty$,
you must also check irreducibility and recurrence (or non-explosion).
Here the jump chain is obviously recurrent, also the process is
dominated by a Poisson process of rate $\lambda$, so cannot explode.
The expected return time to state $i$ is given by $m_i=\{q_i\pi_i\}^{-1}$ so
the mean length of the busy periods is $m_0-q_0^{-1}=\{\lambda
(e^{\lambda /\mu}-1)\}^{-1}$. By considering one call separately we see
$$\E (X_t\mid X_0=i)=e^{-\mu t}+\E (X_t\mid X_0=i-1)=ie^{-\mu t}+\E 
(X_t\mid X_0=0) .$$
Also, in equilibrium,
$$
{\lambda\over\mu}=\E (X_t)=\sum_{i=0}^\infty\pi_i\E (X_t\mid X_0=i)
=\E (X_t\mid X_0=0)+\sum_{i=0}^\infty \frac{e^{-\nu}\nu^i ie^{-\mu t}}{i!}
$$
hence $\E (X_t\mid X_0=i)$.

The chain is reversible, so in equilibrium $N_t$ has the same
distribution as the number of calls starting in $[0,t]$. Indeed the
same argument shows that the joint distribution of $N_{t_1},\ldots
,N_{t_n}$ for $0\leq t_1\leq\cdots\leq t_n$ coincides with that of a
Poisson process, so $(N_t)_{t\geq 0}$ is a Poisson process. This may
be surprising if one is thinking of $(N_t)_{t\geq 0}$ as governed by
$(X_t)_{t\geq 0}$, but remember that $(X_t)_{t\geq 0}$ is in
equilibrium.

\bye
