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

\no{1.1} We have that
$$
\align
\P\bigl(Z_{k+1} = i_{k+1} \bigmid Z_r = i_r \text{ for } 0 \le r \le k\bigr)
&= \P\bigl(X_{m+k+1} = i_{k+1} \bigmid X_{m+r} = i_r 
\text{ for } 0 \le r \le k,\ X_m = i\bigr)\\
&= \P\bigl(X_{m+k+1} = i_{k+1} \bigmid X_{m+k} = i_k\bigr)
\endalign
$$
by the Markov property. The last probability does not depend on 
$i_r$ for $r < k$.  Small step now required.
 

\no{1.2} The sequence $\seq X$ of independent random variables
satisfies
$$\P(X_{n+1}=j\mid X_1=i_1,\dots,X_n=i_n)=\P(X_{n+1}=j),$$
whence the sequence is a Markov chain. The chain is homogeneous
if the $X_i$ are identically distributed.

\no{1.3} With $Y_n$ the outcome of the $n$th throw,
$X_{n+1}=\max\{X_n,Y_{n+1}\}$,
so that
$$p_{ij}=\cases 0&\T{if }j<i\\
\frac16 i&\T{if }j=i\\
\frac16 &\T{if }j>i,
\endcases$$
for $1 \le i,j \le 6$. Similarly,
$$p_{ij}(n)=\cases 0&\T{if }j<i\\
\left(\frac16 i\right)^n&\T{if }j=i.
\endcases$$
If $j>i$, then
$p_{ij}(n)=\P(Z_n=j)$,
where $Z_n=\max\{\seqn Yn\}$, and an elementary calculation
yields
$$p_{ij}(n)=\ga(\frac j6\dr)^n-\ga(\frac{j-1}6\dr)^n,\qq i<j\le6.$$

\no{1.4} (i) There is probably an easier way than the following.
If $X_n=i$, then $X_{n+1}\in\{i-1,i+1\}$. Now,
for $i\ge 1$,
$$\align
\P(X_{n+1}=i+1\mid X_n=i,B) 
&= \P(X_{n+1}=i+1\mid S_n=i,B)\P(S_n=i\mid X_n=i,B) \tag {$\ast$}\\
&\qq +\P(X_{n+1}=i+1\mid S_n=-i,B)\P(S_n=-i\mid X_n=i,B)
\endalign$$
where $B=\{X_r=i_r \T{ for }0\le r<n\}$ and $i_0,i_1,\dots,i_{n-1}$
are integers.
Clearly
$$
\P(X_{n+1}=i+1\mid S_n=i,B)=p,\q
\P(X_{n+1}=i+1\mid S_n=-i,B)=q,
$$
where $p$ ($=1-q$) is the chance of a rightward step. Let $l$ be the time
of the last visit to 0 prior to the time $n$,
$l=\max\{r:i_r=0\}$.
During the time-interval $(l,n]$, the path lies entirely in either
the positive integers or the negative integers. If the former,
it is required to follow the route prescribed by the event
$B\cap\{S_n=i\}$, and if the latter by the event $B\cap\{S_n=-i\}$.
The absolute probabilities of these two routes are
$$\pi_1=p^{\frac12(n-l+i)}q^{\frac12(n-l-i)},\q \pi_2=p^{\frac12(n-l-i)}
q^{\frac12(n-l+i)},$$
whence
$$
\P(S_n=i\mid X_n=i,B)=\frac{\pi_1}{\pi_1+\pi_2}=\frac{p^i}{p^i+q^i}
= 1 - \P(S_n=-i\mid X_n=i,B).
$$
Substitute into ($\ast$) to obtain
$$
\P(X_{n+1}=i+1\mid X_n=i,B) =\frac{p^{i+1}+q^{i+1}}{p^i+q^i}
=1-\P(X_{n+1}=i-1\mid X_n=i,B).
$$
Finally
$\P(X_{n+1}=1\mid X_n=0,B)=1$.  {\it Assuming\/} $X$ is a Markov chain,
its transition probabilities may be calculated more simply by conditioning 
on $S_n$.
\flushpar
(ii) Note that $Y_n \ge 0$.
If $Y_n>0$, then $Y_n-Y_{n+1}$ equals the $(n+1)$th step,
a random variable which is independent of the past history of the process.
If $Y_n=0$ then $S_n=M_n$, so that $Y_{n+1}$ takes the values 0 and 1
with respective probabilities $p$ and $q$, independently of the
past history. [Appealing to an appropriate equation:]
We deduce that  $Y$ is a Markov chain with transition
probabilities
$$\T{for }i>0,\q p_{ij}=\cases p &\T{if }j=i-1
\\q &\T{if }j=i+1,
\endcases
\qq p_{0j}=\cases p &\T{if }j=0\\
q &\T{if }j=1.
\endcases$$
The sequence $Y$ is a random walk with a retaining barrier at 0.

\no{1.5} For any sequence $i_0,i_1,\dots$ of states,
$$\align
\P(Y_{k+1}=i_{k+1}\mid Y_r=i_r  \T{ for }0\le r\le k)
&=\frac{\P(X_{n_s}=i_s \T{ for }0\le s\le k+1)}{\P(X_{n_s}=i_s \T{ for }0\le s\le k)}\\
&=\frac{\prod^k_{s=0}p_{i_s,i_{s+1}}(n_{s+1}-n_s)}
{\prod^{k-1}_{s=0}p_{i_s,i_{s+1}}(n_{s+1}-n_s)}\\
&=p_{i_k,i_{k+1}}(n_{k+1}-n_k)=\P(Y_{k+1}=i_{k+1}\mid Y_k=i_k),
\endalign$$
where $p_{ij}(n)$ denotes the appropriate $n$-step transition probability
of $X$.

With the usual notation, the transition matrix of $Y$ is
$$\pi_{ij}=\cases p^2 &\T{if }j=i+2\\
2pq &\T{if }j=i\\
q^2 &\T{if }j=i-2.
\endcases$$

\no{1.6} Not necessarily\,! Take as example the chains $S$ and $Y$ of
Exercise 1.4. The sum is $S_n+Y_n=M_n$, which is not a
Markov chain.

\no{1.7} A simple way to deal with the first flea is to reduce to a 
two-state chain on $\{$initial vertex, another$\}$ with transition matrix
$\pmatrix0&1\cr\half&\half\cr\endpmatrix$ so that
$$p_{11}(n) =\tfrac13 +\tfrac23 (-\tfrac12 )^n.$$
The second flea has transition
matrix
$$P=\pmatrix 0&\third&\twothirds\cr\twothirds&0&\third\cr
\third&\twothirds&0\cr\endpmatrix.
$$
The eigenvalues of $P$ are $1$, $-{1\over\sqrt 3} e^{\pm i\pi /6 }$ so
$P$ is diagonalizable and
$$p_{11}(n) =\a +\left( -{1\over\sqrt 3}\right)^n \left(\b\cos
{n\pi\over 6} +\gamma\sin {n\pi\over 6}\right)$$
for some constants $\a ,\b ,\gamma$. Then $\a =\third$, $\b
=\twothirds$, $\gamma =0$ by working out $p_{11}(n)$ for $n=0,1,2$.
This method is discussed in the lectures. A very desirable alternative to using
$p_{11}(2)$ is to spot that $p_{11}(n)\to\third$ as $n\to\infty$ by
convergence to equilibrium (not yet proved in lectures), 
which identifies $\a$. An alternative
method altogether is to exploit symmetry to write
$$\eqalign{
&p_{11}(n+1)=\tfrac23 p_{12}(n) +\tfrac13 (1-p_{11}(n)-p_{12}(n))\cr
&p_{12}(n+1)=\tfrac13 p_{11}(n) +\tfrac23 (1-p_{11}(n) -p_{12}(n))\cr}$$
and then solve for $p_{11}(n)$. (Take the first equation. Substituting 
for $p_{12}(n)$ using the second
equation and then for $p_{12}(n-1)$ using the first, you obtain
$3p_{11}(n+1)+ 3p_{11}(n)+p_{11}(n-1)={7\over 3}$ and so obtain the constant
$\alpha=\third$ without using initial conditions or convergence to equilibrium.)

\no{1.8} In the first case the die is like the first flea of the
last question, and
$p=\sixth +\fivesixths (-\fifth )^{n-1}$. By symmetry, 
the other probabilities are 
$\fifth(1-p)$. The second die may be
simulated by throwing the first die but taking 
the $n$th score to be $i_n+n-1$ mod 6,
where $i_n$ is the $n$th score on the first die. 
Hence
$$p=\cases
\sixth +\fivesixths (-\fifth )^{n-1}&\text{if } n=1\  (\text{mod } 6)\cr
\sixth -\sixth (-\fifth )^{n-1}&\text{otherwise}.\endcases
$$ 

\no{1.9} The characteristic polynomial of $P$ is $\third
(x-1)(3x^2+x+p)$. The roots of $3x^2+x+p=0$ are $-\quarter ,-\twelfth$
in case {\rm (a)}, $-\sixth\pm\sixth i$ in case {\rm (b)}, and
$-\sixth$ (twice) in case {\rm (c)}. In fact if $p=\twelfth$, $P$ is
not diagonalizable and the usual trick fails; instead $P$ is similar to
$$\pmatrix-\sixth&1&0\cr 0&-\sixth&0\cr 0&0&1\cr\endpmatrix
$$
so
$p_{11}(n)=\a +(-\sixth )^n (\b +\gamma n)$
for some constants $\a ,\b ,\gamma$ which can be identified as usual.
Another approach is to solve the system of recurrences
$$\eqalign{
&p_{11}(n+1) =p\ldotp p_{13}(n)\cr
&p_{12}(n+1)=p_{11}(n) +\tfrac23 p_{12}(n) +(1-p)p_{13}(n)\cr
&p_{13}(n+1)=\tfrac13 p_{12}(n)\cr}$$
coming from the Chapman--Kolmogorov equations. 
Using $p_{11}(n)+p_{12}(n)+p_{13}(n)=1$ and proceeding 
as in Exercise 1.7 you obtain
$3p_{11}(n+1)+ p_{11}(n) + p.p_{11}(n-1)= p$ which can be solved in the usual
way. Using this method you obtain the constant term $p/(p+4)$ in the general
case without using initial conditions.

\no{1.10} Classes $\{ 1,5\}$ and $\{ 3\}$ are closed.

\no{1.11} If the communicating class of $i$ is not closed, there exists
$j$ with $i\to j$, $j\nrightarrow i$. Suppose there is no closed class. Then
we get a sequence $i_1,i_2,\ldots$ of states with $i_n\to i_{n+1}$,
$i_n\nrightarrow i_{n+1}$. There can be no repeats, so the state-space is
infinite.

\no{1.12} Set $h_i=\P_i (\hbox{hit 10})$ then
$$
h_2=\tfrac12 h_4,\ 
h_4=\tfrac12 h_8,\ 
h_8=\tfrac12 h_6+\tfrac12,\ 
h_6=\tfrac12 h_2+\tfrac12.
$$
Hence $h_2=\frac15$. Set $k_i=\E_i(\text{time to hit 0 or 10})$, then
$k_2=k_8$ and $k_4=k_6$, by symmetry. Also
$k_2=1+\half k_4$ etc,
so $k_2=2$. Students should be encouraged to spot and use
the symmetry in this question.

\no{1.13} The calculation of hitting probabilities for a general birth and
death chain will be discussed in lectures. Set $h_i=\P_i(\text{hit }0)$, then
$h_0=1$ and
$$h_i=p_{i,i+1}h_{i+1}+p_{i,i-1}h_{i-1}$$
so $u_i=h_{i-1}-h_i$ satisfies $u_i \ge 0$,
$$u_{i+1}={p_{i,i-1}\over p_{i,i+1}} u_i=\left({i\over i+1}\right)^2
u_i=\dots = \left({1\over i+1}\right)^2 u_1,$$
and
$$h_i=h_0-(h_0-h_i)=1-u_1\sum_{j=1}^i {1\over j^2}\; .$$
Since $(h_i:i\geq 0)$ is the minimal non-negative solution, we have that
$$u_1=\biggl(\sum_{j=1}^\infty {1\over j^2}\biggr)^{-1}
={6\over\pi^2}$$
and
$$\hbox{$\displaystyle{\P_0(X_n\geq 1}$ for all $\displaystyle{n\geq
1)=1-h_1={6\over\pi^2} .}$}$$

\no{1.14} By conditioning on $X_1$ and using shift invariance and the strong
Markov property, we obtain that
$$
\phi = \tfrac12\E(s^{H_0}\mid X_1 = 2) + \tfrac12\E(s^{H_0}\mid X_1 = 0)
= \tfrac12 s\phi^2 + \tfrac12 s.
$$
whence $\phi(s) =\{ 1 \pm \sqrt{1-s^2}\}/s$.  Now 
$\phi(0)= 0$, and $\phi(s)$ is continuous  
on $[0,1)$; hence $\phi(s) = \{1 - \sqrt{1-s^2}\}/s$.  For the second part,
$$
\phi=\tfrac12\E (s^{H_0}\mid X_1=3)+\tfrac12\E (s^{H_0}\mid X_1=0)
=\tfrac12 s\phi^3+\tfrac12 s.
$$

\bye
