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

\no{2.1} Let $i$ ($\ne s$) be a state of the chain, and define
$n_i=\min\{n:p_{is}(n)>0\}$.
If $X_0=i$ and $X_{n_i}=s$ then, with probability one,
$X$ makes no visit to $i$ during the intervening
period $[1,n_i-1]$; this follows from the minimality
of $n_i$. Now $s$ is absorbing, and hence
$$\P(\T{no return to }i\mid X_0=i)\ge \P(X_{n_i}=s\mid X_0=i)>0.$$

\no{2.2} If $r=1$, then state $i$ is absorbing for $i\ge 1$;
also, 0 is transient unless $a_0=1$.

Assume $r<1$ and let
$J=\sup\{j:a_j>0\}$.
The states $0,1,\dots,J$ form an irreducible
persistent class; they are aperiodic if $r > 0$. All other states are transient.
For $0\le i\le J$, the recurrence time $T_i$ of $i$ satisfies
$\P(T_i = 1) = r$. If $T_i > 1$ then $T_i$ may be expressed as the sum
of
$$\align
T_i^{(1)} &:=\hbox{ time to reach 0, given that the first step is leftwards,}\\
T_i^{(2)} &:=\hbox{ time spent in excursions from 0 not reaching  $i$,}\\
T_i^{(3)} &:=\hbox{ time taken to reach  $i$ in final excursion.}
\endalign$$
It is easy to see that
$\E\bigl(T_i^{(1)}\bigr)=1+(i-1)/(1-r)$ if $i \ge 1$,
since the waiting time at each intermediate point has mean
$(1-r)^{-1}$. The number $N$ of such `small' excursions has
mass function
$\P(N=n)=\a_i(1-\a_i)^n$, $n\ge 0$,
where
$\a_i=\sum^{\oo}_{j=i} a_j$;
hence
$\E(N)=(1-\a_i)/\a_i$. Each such small excursion has mean duration
$$\sum^{i-1}_{j=0} \ga(\frac j{1-r} + 1\dr)\frac{a_j}{1-\a_i}
=1+\sum^{i-1}_{j=0} \frac{ja_j}{(1-\a_i)(1-r)}$$
and therefore
$$\E\bigl(T_i^{(2)}\bigr) =
\frac1{\a_i}\biggl\{(1-\a_i)+\sum^{i-1}_{j=0} \frac{ja_j}{1-r}\biggr\}.$$
By a similar argument,
$$\E\bigl(T_i^{(3)}\bigr) =
\frac1{\a_i}\sum^{\oo}_{j=i}\ga(1+\frac{j-i}{1-r}\dr)a_j.$$
Combining this information, we obtain that
$$\E(T_i)=r + (1-r)\E\bigl(T_i^{(1)}+T_i^{(2)}+T_i^{(3)}\bigr)
= \frac1{\a_i}\biggl(1-r+\sum^{\oo}_{j=0}
ja_j\biggr),\q i \ge 1,$$
and a similar argument yields $\E(T_0) = 1 + \sum_j ja_j/(1-r)$.
The apparent simplicity of these formulae
suggests the possibility of an easier
derivation; see Exercise (6.4.25).
Clearly $\E(T_i)<\oo$ for $i\le J$ whenever
$\sum_j ja_j<\oo$, a condition which  certainly holds if $J < \oo$.

Alternatively, compute the invariant distribution $\pi$, and set $\E(T_i) =
1/\pi_i$.

\no{2.3} All states are absorbing if $p=0$. Assume henceforth that
$p\ne 0$. Diagonalize $\B P$ to obtain
$\B P=\B B\boldLambda \B B^{-1}$
where
$$\gather
\B B = \ga(\matrix 1&1&1\\1&0&-1\\1&-1&1\endmatrix\dr),\q
\B B^{-1} = \ga(\matrix \frac14&\frac12&\frac14\\\frac12&0&-\frac12\\
\frac14&-\frac12&\frac14\endmatrix\dr),\\
\boldLambda = \ga(\matrix 1&0&0\\0&1-2p&0\\0&0&1-4p\endmatrix\dr).
\endgather $$
Therefore
$$\B P^n=\B B\boldLambda^n \B B^{-1}
= \B B \ga(\matrix 1&0&0\\0&(1-2p)^n&0\\0&0&(1-4p)^n
\endmatrix\dr)\B B^{-1}$$
whence $p_{ij}(n)$ is easily found.

In particular,
$p_{11}(n)=\tfrac14+\tfrac12(1-2p)^n+\tfrac14(1-4p)^n$.

\no{2.4}(a) By symmetry, all states have the same mean-recurrence
time. Using the renewal-process argument of the last solution,
the common value equals 8, being the number of vertices of the
cube. Hence $\mu_v=8$.

Alternatively, let $s$ be a neighbour of $v$, and let $t$ be a
neighbour of $s$ other than $v$. In the obvious notation,
by symmetry,
$$\alignat 2
\mu_v&=1+\tfrac34\mu_{sv},
&\q\mu_{sv}&=1+\tfrac14\mu_{sv}+\tfrac12\mu_{tv},\\
\mu_{tv}&=1+\tfrac12\mu_{sv}+\tfrac14\mu_{tv}+\tfrac14\mu_{wv},
&\q\mu_{wv}&=1+\tfrac14\mu_{wv}+\tfrac34\mu_{tv},
\endalignat$$
a system of equations which may be solved to obtain $\mu_v=8$.
\flushpar
(b) Using the above equations, $\mu_{wv}=40/3$,
whence $\mu_{vw}=40/3$ by symmetry.
\flushpar
(c) The required number $X$ satisfies
$\P(X=n)=\theta^{n-1}(1-\theta)^2$ for $n\ge 1$,
where $\theta$ is the probability that the first return
of the walk  to its
starting point precedes its first visit to the
diametrically opposed vertex. Therefore
$$\E(X)=\sum^{\oo}_{n=1} n\theta^{n-1}(1-\theta)^2=1.$$

\no{2.5} This is just to check they have registered that recurrence and
transience are class properties, and a finite class is recurrent if
and only if it is closed.

\no{2.6} The chain is transient if and only if $\sum_{j=1}^\infty 
j^{-\a} <\infty$ by the calculation of 1.13. Transience means only
finitely many visits to each state, recurrence means infinitely many
visits to every state, and one or the other holds. Hence
$$
\P (X_n\to\infty \text{ as } n\to\infty
)=
\cases 1&\text{if } \a >1\cr
0&\text{if } \a\leq 1.
\endcases
$$
Students may not notice that the $\a\le 1$ case gives a recurrent walk
even though there is a greater tendency to move right than left.

\no{2.7} Draw the tree! Set $X_n$ to be the distance from $R$
at time $n$. Then
$(X_n)_{n\geq 0}$ is a biased random walk on $\{ 0,1,\ldots\}$ with
$p_{i,i+1}=\twothirds$, $p_{i,i-1}=\third$, which is known to be
transient, so the random walk on $T$ is certainly transient.

\no{2.8} Project onto $\Z^3$ and remove times at which the walk stays
still (using the strong Markov property). So obtain the simple symmetric
random walk in $\Z^3$ which is known to be transient.

\no{2.9} Invariant distributions are $\{ (\half p,0,1-p,0,\half p)$:
$0\leq p\leq 1\}$. The point is to show how non-uniqueness occurs when
the matrix is not irreducible.

\no{2.10} The state-space is $\{ 0,1,\ldots ,N\}$ and the transition
probabilities are given by
$$p_{i,i+1}+p_{i,i-1}=1,\q p_{i,i-1}={i\over N}\, ,\q i=1,\ldots ,N\, .$$
The underlying physical model makes it clear that the equilibrium
distribution is
$\text{Bin}(N,\half )$, which may also be discovered more
laboriously from the transition probabilities.

\no{2.11} Students must be drilled to check for irreducibility and
aperiodicity before using\nl
$p_{ij}(n)\rightarrow\pi_j$ for an
invariant distribution $\pi$.

\no{2.12} The invariant distribution $\pi$ satisfies $\pi_1=p\pi_3$ and
$\pi_3=\third\pi_2$, so $\pi=(p,3,1)/(p+4)$.

\no{2.13} Draw the flow diagram, symmetrically. The invariant measure
$\pi$ satisfies
$$
\pi_{123} =\a_1(\pi_{123}+\pi_{231}+\pi_{213}), \q
\pi_{132}=\a_1 (\pi_{132}+\pi_{312} +\pi_{321})
$$
so $\pi_{123}+\pi_{132}=\a_1$, similarly $\pi_{231}+\pi_{213}=\a_2$
and $\pi_{123}=\a_1(\pi_{123}+\a_2)$.

\no{2.14} This is partly covered in lectures. Try to solve the detailed
balance equations $\pi_ip_{ij}=\pi_j p_{ji}$. In case {\rm (b)} no
solution exists if $p\not=\half$. In case {\rm (c)} there is no
solution with $\sum_{i=0}^\infty\pi_i=1$ if $p\geq\half$. Otherwise
$P$ is reversible. It may be worth stressing that all birth and death processes
are reversible and that this is a good way to find invariant distributions
for such processes. 


\no{2.15} Look for a solution to the equations $\pi_ip_{ij}=\pi_jp_{ji}$.
The only non-trivial cases of interest are those with $j=i+1$, and therefore
$\lambda_i\pi_i=\mu_{i+1}\pi_{i+1}$ for $0\le i<b$,
with solution
$$\pi_i=\pi_0\frac{\lambda_0\lambda_1\cdots\lambda_{i-1}}{\mu_1\mu_2\cdots\mu_i},
\qq0\le i\le b,$$
an empty product being interpreted as 1.
The constant $\pi_0$ is chosen in order that the $\pi$'s sum to 1, and
the chain is therefore time-reversible.

\no{2.16} Let  $\pmb\pi$ be the stationary distribution of $X$,
and suppose $X$ is time-reversible. We have that $\pi_ip_{ij}=
p_{ji}\pi_j$ for all $i,j$, and furthermore $\pi_i>0$
for all $i$. Hence
$$\pi_ip_{ij}p_{jk}p_{ki}=p_{ji}\pi_jp_{jk}p_{ki}=
p_{ji}p_{kj}\pi_kp_{ki}=p_{ji}p_{kj}p_{ik}\pi_i$$
as required when $n=3$. A similar calculation is valid
when $n>3$.

Suppose conversely that the given display holds for all finite
sequences of states. Sum over all values of the subsequence
$j_2,\dots,j_{n-1}$ to deduce that
$p_{ij}(n-1)p_{ji} = p_{ij}p_{ji}(n-1)$,
where $i=j_1$, $j=j_n$. Take the limit as $n\to\oo$
to obtain $\pi_jp_{ji}=p_{ij}\pi_i$ as required
for time-reversibility.

\bye
