\magnification=1200
\parindent=10pt
\input probmacros
%%
\line {\bf IB/IIA --- Michaelmas 2000\hfil GRG}
\line{\hfil \tt g.r.grimmett{\@}statslab.cam.ac.uk}
\bigb
\cl {\bf MARKOV CHAINS}
\med
\cl {\bf Example Sheet 1}
\bigb

\no{1.1} Let
 $X = (X_n)$ be a Markov chain.  Suppose that we are
given that $X_m = i$.  Show that $Z_k = X_{m+k}$, $k \ge 0$,
is a Markov chain with starting state $i$.

\no{1.2}Show that any sequence of independent random variables taking values in the
countable set  $S$  is a Markov chain.  Under what condition is this chain 
homogeneous?


\no{1.3}Let  $X_n$  be the maximum reading obtained in the first  $n$  throws of a
fair die.  Show that  $X$  is a Markov chain, and find the transition 
probabilities  $p_{ij}(n)$.


\no{1.4}Let  $\{S_n: n \geq  0\}$  be a simple random walk with	$S_0 = 0$,  and
show that  $X_n = |S_n|$  defines a Markov chain; find the transition probabilities
of this chain.	Let  $M_n = \max \{S_k: 0
\leq  k \leq  n\}$,  and show that  $Y_n = M_n - S_n$  defines a Markov chain.


\no{1.5}Let  $X$  be a Markov chain and 
let  $\{n_r: r \geq  0\}$  be an unbounded
increasing sequence of positive integers.  Show that  $Y_r = X_{n_r}$
constitutes a (possibly inhomogeneous) Markov chain.  Find the transition 
matrix of  $Y$	when  $n_r = 2r$  and  $X$  is
a simple random walk.


\no{1.6} Let $X$ and $Y$ be Markov chains on the set $\Bbb Z$ of
integers.  Is the sequence $Z_n = X_n + Y_n$ necessarily a Markov chain?
Explain.

\no{1.7} A flea hops about at random on the vertices of a triangle (i.e.,\ each
hop is from the currently occupied vertex to one of
the other two vertices each with probability $1\over 2$).
Find the probability that after $n$ hops the flea is back where it
started.

A second flea also hops about on the vertices of a triangle, but this
flea is twice as likely to jump clockwise as anticlockwise. What is
the probability that after $n$ hops this second flea is back where it
started?
\smallskip\noindent
[{\it Hint\/}: ${1\over 2}\pm {i\over 2\sqrt 3} ={1\over\sqrt 3}\,
e^{\pm i\pi /6}$.]

\no{1.8} A die is `fixed' so that when it is rolled the score
cannot be the same as the previous score, all other scores having
probability $\frac15$. If the first score is 6, what is the probability $p$
that the $n$th score is 6? What is the probability that the $n$th score
is $j$, where $j\ne 6$?

Suppose instead that the die cannot score one greater (mod 6) than the
previous score, all other five scores having equal probability. What is
the new value of $p$? 

\noindent
[{\it Hint\/}: Think about the relationship between the two dice.]


\no{1.9} Let $(X_n)_{n\geq 0}$ be a Markov chain on $\{ 1,2,3\}$
with transition matrix
$$P=\pmatrix 0&1&0\\ 
              0&\frac23&\frac13\\ 
              p&1-p&0\endpmatrix .
$$
Calculate $\P (X_n=1\mid X_0=1)$ in each of the following cases (a)
$p=\frac1{16}$, (b) $p=\frac16$,
\newline
(c)$^*$ $p=\frac1{12}$.

\no{1.10} Identify the communicating classes of the transition
matrix
$$
P=\pmatrix
\frac12&0&0&0&\frac12\\ 
0&\frac12&0&\frac12&0\\
0&0&1&0&0\\ 
0&\frac14&\frac14&\frac14&\frac14\\
\frac12&0&0&0&\frac12\endpmatrix .
$$
Which of the classes are closed?

\no{1.11} Show that every transition matrix on a finite state-space
has at least one closed communicating class. Find an example of a
transition matrix with no closed communicating class.

\no{1.12}  A gambler has {\it\$}2 and needs to increase it to {\it\$}10 
in a hurry.  He can play a game with the following rules:  a fair coin is 
tossed; if a player bets on the side which actually
turns up, he wins a sum equal to his stake, 
and his stake is returned; otherwise he loses his stake.  The gambler 
decides to use a bold strategy in which he stakes all his money if he has 
{\it \$}5 or less, and otherwise  stakes just enough to increase his capital, 
if he wins, to {\it\$}10.

Let $X_0=2$ and let $X_n$ ($n \geq 1$) be his capital after $n$ throws.  Prove 
that the gambler will achieve his aim with probability $\frac15$.

What is the expected number of tosses until the gambler either achieves his 
aim or loses his capital?

\no{1.13} Let $(X_n)_{n\geq 0}$ be a Markov chain on $\{ 0,1,\ldots\}$
with transition probabilities given by
$$
p_{0,1}=1,\q p_{i,i+1}+p_{i,i-1}=1,\q p_{i,i+1}=\left({i+1\over
i}\right)^2 p_{i,i-1},\q i\geq 1.$$
Show that if $X_0=0$ the probability that $X_n\geq 1$ for all $n\geq
1$ is $6/\pi^2$.

\no{1.14} Let $Y_1,Y_2,\ldots$ be independent identically
distributed random variables with
$\P (Y_1=1)=\P (Y_1=-1)=\frac12$ and
set $X_0=1$, $X_n=X_0+Y_1+\cdots +Y_n$ for $n\geq 1$. Define
$$H_0=\inf\{ n\geq 0:X_n=0\}\, .$$
Find the probability generating function $\phi (s)=\E (s^{H_0})$.

Suppose the distribution of $Y_1,Y_2,\ldots$ is changed to $\P
(Y_1=2)=\P (Y_1=-1)=\frac12$. Show that $\phi$ now satisfies
$$s\phi^3-2\phi +s=0.$$
\bye
