\magnification=1200
\parindent=10pt
\input probmacros
%%
\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 2}
\bigb

\no{2.1}Let  $X$  be a Markov chain containing an absorbing state  $s$  to which
all other states lead (i.e., $j \to s$ for all $j$).  
Show that all states other than  $s$  are 
transient.


\no{2.2}Let $X$ be a Markov 
chain on  $\{0,1,2,\dots \}$  with transition matrix
given by
$p_{0,j} = a_j$ for $j \geq  0$,
$p_{i,i} = r$ and  $p_{i,i-1} = 1 - r$ for  $i \geq 1$.
Assume that $0 < r < 1$.
Classify the states of the chain, and find their mean recurrence times.
[You may find it useful to define $J=\sup\{j:a_j>0\}$.]

\no{2.3}Compute $p_{11}(n)$ and classify the 
states of the Markov chain with state space $S = \{1,2,3\}$
and transition matrix
$$
\pmatrix
1-2p &2p &0\\
p &1-2p &p\\
0 &2p &1-2p
\endpmatrix.
$$

\no{2.4}A particle performs a random walk on the vertices of a cube.  At each step
it remains where it is with probability  $\frac14 $,  and moves to each of its 
neighbouring vertices with probability  $\frac14 $.  Let  $v$  and  $w$  be two
diametrically opposite vertices.  If the walk starts at  $v$,  find 
\ii{(a)} the mean number of steps until its first return to  $v$,
\ii{(b)} the mean number of steps until its first visit to  $w$,
\ii{(c)} the mean number of visits to  $w$  before its first return to  $v$.

\no{2.5} In Exercise 1.10, which states are recurrent and which are
transient?

\no{2.6} What can be said about the number of visits to each state in
the case where (a) a Markov chain is transient, and (b) a Markov chain is
recurrent? 

Consider the Markov chain $(X_n)_{n\geq 0}$ of
Exercise 1.13.  Show for this chain that
$\P (X_n\to\infty \text{ as }n\to\infty)=
\P(\forall m,\ \exists n.\ X_N\ge m\text{ for all }N\ge n)=1$.

Suppose the transition probabilities satisfy instead
$$p_{i,i+1}=\left({i+1\over i}\right)^\a p_{i,i-1}.$$
For each $\a\in (0,\infty )$ find the value of $\P
(X_n\to\infty$ as $n\to\infty )$.

\no{2.7} The rooted binary tree is an infinite graph $T$ with one
distinguished vertex $R$ from which comes a single edge; at every
other vertex there are three edges and there are no closed loops. The
random walk on $T$ jumps from a vertex along each available edge with
equal probability. Show that the random walk is transient.

\no{2.8} Show (by projection onto $\Z^3$ or
otherwise) that the simple symmetric random walk in $\Z^4$ is
transient.

\no{2.9} Find all invariant distribution of the transition matrix
in Exercise 1.10.

\no{2.10} Two containers A and B are placed adjacently to one another, and
gas is allowed to pass through a small aperture joining them.
There are $N$ molecules in all, and we assume that, at each
epoch of time, one molecule (chosen at random)
passes through the aperture.
Show that
the number of molecules in A evolves as a Markov chain. What
are the transition probabilities? What is the invariant distribution
of this chain? [This is the `Ehrenfest urn model', first introduced by
Ehrenfest under the name `dog-flea model'.]


\no{2.11} A fair die is thrown repeatedly.  Let $X_n$ denote the sum of
the first $n$ throws. Find
$$\lim \limits_{n \to \infty} \Bbb P (X_n \hbox{ is a multiple of 13})$$
quoting carefully any general theorems that you use.

\no{2.12} Find the invariant distributions of the transition
matrices in Exercise 1.9, parts (a), (b) and (c),
and compare them with your answers to that exercise.

\no{2.13} Each morning a student takes one of the three books 
(labelled 1, 2, 3) he
owns from his shelf.  The probability that he chooses the book 
with label $i$ is
$\a_i$ (where  $0< \a_i<1$, $i=1,2,3$), and choices on successive days are
independent.  In the evening he replaces the book at the left-hand end
of the shelf.  If $p_n$ denotes the probability that on day $n$ the
student finds the books in the order 1,2,3, from left to right, show
that, irrespective of the initial arrangement of the books, $p_n$
converges as $n \to \infty$, and determine the limit.

\no{2.14} In each of the following cases determine whether the
stochastic matrix $P$ corresponds to a chain which is reversible in equilibrium:
\med
\i{} (a)\q$\displaystyle{\pmatrix p&1-p\cr q&1-q\cr\endpmatrix ;}$
\hskip.5truein
(b)\q$\displaystyle{\pmatrix 0&p&1-p\cr 1-p&0&p\cr p&1-p&0\cr\endpmatrix ;}$
\bigb
\i{} (c)\q $I=\{ 0,1,2,\ldots\}$ and $p_{01}=1$, $p_{i,i+1}=p$,
$p_{i,i-1}=1-p$ for $i\geq 1$.
\i{} (d)\q $p_{ij}=p_{ji}$ for all $i,j \in S$.



\no{2.15}A random walk on the set $\{0,1,2,\dots ,b\}$  has transition matrix given by
$p_{00} = 1 - \lambda _0$, $p_{bb} = 1 - \mu _b$,
$p_{i,i+1} = \lambda _i$ and $p_{i+1,i} =
\mu _{i+1}$  for  $0 \leq  i < b$,
where  $0 < \lambda _i, \mu _i < 1$  for all  $i$,  and  $\lambda _i +
\mu _i = 1$  for  $1 \leq  i < b$.  Show that this process is time-reversible
in equilibrium.


\no{2.16}Let  $X$ be an irreducible non-null persistent aperiodic
Markov chain.  Show that
$X$  is time-reversible in equilibrium if and only if
$$
p_{j_1j_2}p_{j_2j_3}\cdots p_{j_{n-1}j_n}p_{j_nj_1} =
p_{j_1j_n}p_{j_nj_{n-1}}\cdots p_{j_2j_1}
$$
for all $n$ and all finite sequences  $j_1,j_2,\dots,j_n$  of states.


\bye
\bigb
{\bf Appendix -- guide to past Tripos questions}
\med
\halign{\indent#&&#\hfil\q\cr
&1.1&IB&91/4/8*\cr
&1.3&IB&87/1/7, 88/1/8(i), 89/1/8*, 90/1/8, 94/5/1\cr
&1.6&IB&88/1/8(ii)\cr
&&IIA&94/1/1\cr
&1.7&IB&89/3/7, 91/1/8, 92/3/7, 93/5/2, 94/5/2\cr
&1.8&IB&87/2/6, 88/4/8*, 90/3/7, 92/1/8*, 93/5/1\cr
&1.9&IB&87/3/7, 92/4/8\cr
&&IIA&94/2/1 ((i) and first part of (ii))\cr
&1.10&IB&89/4/8, 91/3/7\cr}



\bye
