Exercise 1. Triangle Consider the 3-state Markov chain with transition probabilities:

●  1 → 2 with probability 1

● 2 → 3 with probability 1/2

● 2 → 1 with probability 1/2

● 3 → 2 with probability 1/2

● 3 → 1 with probability 1/2

(a)  Make a graph of the Markov chain

(b) Find the communication classes and periods.

(c) Find the invariant measure.

(d) What is the average return time to state 3?

(e) Assume you start from 1, what is in average the time it takes you to reach 3 for the first

time?

I give some calculations, some are useful for the problem, some are useless, choose wisely!

╱I _  、、− 1 =  ╱ 2(4)   4(2) 、  and  ╱I _  、、− 1 = ╱ 1(2)   2(2) 、.

Solution:

(a)

(b)  In the closed loop 1 → 2 → 3 → 1, each transition has positive probability (1,  , ), so all

states communicate with each other and the chain is irreducible .  The chain is aperiodic . Indeed, considering for instance the period of state 1, we have P1(2)1  > 0 (since 1 → 2 → 1 has strictly positive probability) and P1(3)1  has positive probability (from the loop mentioned above) .  The period of 1 thus divides 2 and 3, and therefore d(1) = 1 which is the period of all elements of the class as well.

(c)   We need to solve πP = π .  This provides the system of equations:

(ìπ 1  ( π2 ì(ì)π3

=  (π2 + π3 )

= π 1 + π3

= π2 .

The  last  equation provides  π2   in  terms  of π3 .   I can  inject  this  in  the first  or second equation,  and get  (for instance  using the  2nd equation) π 1 + π3  = π2  = 2π3 ,  yielding π 1 = π3 .  To find π3  we use the normalization condition:

π 1 + π2 + π3 = π3 (  + 2 + 1) = π3 = 1.

All together, this yields π = ( ,  , ) .

(d)  A theorem seen in class tells us that in an irreducible aperiodic chain the average return time to  a given state is the inverse of the invariant distribution.  Therefore,

E[T3] =  1  = 9

(e)  To answer this question we will use the fundamental matrix ideas developed for transient

states .  Here, no state is transient, but defining a new Markov chain with 3 being an ab- sorbing state (i. e .  P33 = 1) and all other transitions being identical, what happens before hitting 3 in the  original Markov chain is identical to what happens  before  absorption at 3 in the new Markov chain.   Therefore,  the number of steps  before hitting 3 in the first Markov  chain is  the same  as  the number of steps  before  absorption in the new Markov chain.  We have seen that the average number of steps before absorption can be computed through the associated fundamental matrix.

To compute that matrix, we reorder the states starting with absorbing state first, and use the order (3, 1, 2) .  We get the following matrix:

╱、

| 1/2  1/2   0 |

Therefore, P2 =  、  and the associated fundamental matrix is: ╱ 1(2)   2(2) 、

Multiplying this matrix by the vector  ╱ 1(1)、(or just summing over the rows), we find that the average time before reaching state 3 starting from 1 is 4, and the average time before reaching state 3 starting from 2 is 3.

Exercise 2. Consider the Markov chain with state space H = {0, 1, 2, 3, 4, 5} and transition matrix:

╱     、

．(．)     0      0     .1    0     .9     0    ．(．)

．(．)   .25   .25    0    0    .25   .25   ．(．)

．    0      0     .7    0     .3     0    ．

(a)  Make a graph of the chain. What are the communication classes? Indicate for each if it is recurrent or transient, and compute the period for each class.

(b)  Consider X0  = 0.  Does the probability distribution of the Markov chain converge?  If this is the case, find the limit when n → o of P[Xn = 0IX0 = 0] and P[Xn = 1IX0 = 0]. What is the expectation of the first return time to 0?

(c)  Compute the limit, when n → o, of the probability P[Xn = 4IX0 = 0].

(d) Assume now that the chain starts at 3.  Compute the probability, in the long run, to find the chain in the class 0, 1? Same question when the chain starts at 5.

[Hint]:  Please verify that the fundamental matrix is

 ╱ 4(12)   20(5) 、

.  If you use these results,  explain in your copy why these matrices are indeed correct.

Solution:

(a)

The  communication class  associated with 0 is {0, 1} because  0 and 1  communicate with each  other,  and neither 0 nor 1  can reach  any other state .   This  class is thus recurrent because it is closed.  The period is 1  because P00  > 0 .

The  communication  class  associated with  2  is  {2, 4},  it  is  recurrent  with period  1, for analogous reasons .

The communication class associated with 3 is {3, 5} because 3 and 5 communicate directly with each other and all other states are in other communication classes, so I don’t even need to check again that they do not communicate with 3, it has already been addressed. The period is 1  because P55  > 0 .  It is transient because it is not closed, P31  > 0 .

(b)   Yes, the probability distribution converges .  Since {0, 1} is a closed communication class,

I know that the Markov chain will only alternate between these two states when starting from X0 = 0 and will never reach any of the states 2,3,4,5.  The probability for Xn  to be at any of these states is thus 0 for all n, which converges to 0.  The probability distribution of states 0 and 1 behave exactly like the probabilities of a standard 2-state Markov chain. This  2-state  Markov  chain  is  irreducible  and  aperiodic,  thus  converges  to  its  invariant distribution, which has already been computed several times .  Here, p = 1/2, q = 0.3, so the  invariant measure  of the  two-state  Markov  chain  is  (q/(p + q), p/(p + q)) = ( , ) and the probability distribution of our Markov chain converges to

(  ,  , 0, 0, 0, 0).

Moreover, the expected return time to 0 is  =  .

(c)  Since starting from 0 the Markov chain cannot reach 4, we have for all n P[Xn = 4IX0 = 0] = 0 which converges to 0 .

(d)  3 is  a transient state .   The probability to  be  absorbed in the  class  {0, 1} is given  by the theory  of the fundamental  matrix.    We  rewrite  the  matrix  with  recurrent  states first, and  obtain  (for  simplicity  I  do  not  rewrite  the  numbers  that  are  not  relevant  to  my calculations and replace them by crosses when they are non-zero):

so P2  =   、.   To  verify  that the fundamental matrix is  as given,  I multiply

I _ P2 with  the  matrix given,  and I do find the 2 x 2 identity matrix.   The probability to  reach  a given  recurrent state  starting from  a  transient state  is found  by multiplying the fundamental matrix with the matrix Q which is the lower- left block of the reordered matrix.

and then we conclude that the probability to  end up in the class {0, 1},  being the sum of the probability to reach 0 or 1 first,  :

●  starting from 3,   .

●  starting from 5,   .

Exercise 3.  Small vs Big Foot Random  Walk

We compare here two random walks on {0, 1, 2, 3, 4, 5}, both with absorbing conditions.

The first model is the standard random walk, where p(n, n + 1) = 1/2 for all 0 < n < 5 and p(n, n _ 1) = 1/2 for all 0 < n < 5, with boundary conditions p(0, 0) = p(5, 5) = 1.

The second model is the ‘big foot’ random walk where the walker can only do steps of size 2, i.e., p(n, n + 2) = 1/2 for 1 s n s 3 and p(n, n _ 2) = 1/2 for 2 s n < 5, with:

(ìp(4, 5) = 1/2

ì(ì)p(5, 5) = 1

(a)  Compute the communication classes for both chains and the indicate which ones are recurrent or transient.

(b)  Compute the average time spent before absorption for each possible initial condition for the standard random walk.

(c)  Compute the probability to be absorbed at 0 starting from any initial condition.

(d)  Do the same for the big foot random walk.

(e) Assume you started from the initial condition X0  = 1. Is it more likely to be absorbed

at 0 for the standard random walk than for the big foot random walk? How about the case X0 = 2? Can you interpret these results?

Hint: you may be happy to know that:

┌     1 !(!)     0

!

!(!) _1/2

'

and that:

┌     1    !(!) _1/2

!

!(!)     0

'

Solution:

0

1

0

_1/2

_1/2

1

_1/2

0

_1/2 0   1

0

0

_1/2

1

_1/2

_ /2  − 1 =   ┌!!!!!    

'            '

_ /2  − 1 =   ┌!!!!!    

1     '            ' 2    4

(a)  For the normal random walk, {0} is  a communication class  on its  own,  as well as {5},

and they are recurrent, because both are absorbing states .  {1, 2, 3, 4} is a communication class because each transition in the closed loop 1 → 2 → 3 → 4 → 3 → 2 → 1 has strictly positive probability.  It is transient because the Markov chain has a positive probability to leave this class at 1 or 4 .

For big foot random walk, {0} is a communication class on its own, as well as {5}, and they are recurrent.  The communication class of state 1 is {1, 3}.  Indeed, 1 and 3 clearly communicate, and they cannot reach 2 or 4 .  Similarly, {2, 4} is a communication class . Both  {1, 3} and {2, 4} are  transient  because  there  is  a positive probability  to  leave  the class .

(b)  I rewrite my transition matrix with the states ordered as (0, 5, 1, 2, 3, 4) .  You should find

╱  0        1/2    0        0      、                    ╱  1/2    0      、

that P2  =   /2   /2   /(/)2(2)   /2  and Q =          /2  .  The fundamental matrix

is the second one given in the hint.

The  time  before  absorption is  the  sum  over the  rows  of the fundamental matrix,  so  we get an average time of

● 4 steps when starting from 1

●  6 steps when starting from 2

●  6 steps when starting from 3

● 4 steps when starting from 4

(c)  the probability  to  be  absorbed  at  a  given  recurrent  state  is  given  by  the product  of the fundamental matrix by Q .  It is easy to see that the product of the matrix gives:

1  ╱．3(4)   2(1) 、．

5  ．   2   3   ．