Question

 Consider the Markov chain on state space {1,2, 3,4, 5, 6}. From 1 it goes to 2 or 3 equally likely. From 2 it goes back to 2. From 3 it goes to 1, 2, or 4 equally likely. From 4 the chain goes to 5 or 6 equally likely. From 5 it goes to 4 or 6 equally likely. From 6 it goes straight to 5.

 (a) What are the communicating classes? Which are recurrent and which are transient? What are their periods?

 (b) Write the transition matrix for this Markov chain. Since it is stochastic, it has at least one eigenvalue of multiplicity 1. What is is the multiplicity of the eigenvalue 1? (Note: the multiplicity of 1 should match the number of recurrent communicating classes.)

 (c) Find two different invariant measures for this Markov chain. Can you construct. infinitely many invariant measures?

 (d) If you start the Markov chain at 1, what is the expected number of returns to 1? Compute this in two ways:

 i. By observing that from 1 you can go to 2, you can go to 3 then leave to 2 or to 4, or you can go to 3 then return to 1. With the first three moves you will never return to 1. Reduce this problem to a much simpler Markov chain and find the mass function of the number of total times you return to 1, i.e. the probability it equals 0, 1, 2, etc. Now compute the average number of returns to 1.

 ii. Use the linear algebra method you learned in class. In this case, compute also the average number of visits to 3, starting at 1. Starting at 1, what is the average number of steps it takes before you leave the transient class forever?

 (e) Starting at 1, what is the probability you will ever reach 2? Again, compute this in two ways:

 i. Let p be the probability we are after. Now observe that starting at 1 you can go to 2 directly, go to 3 then to 4 and thus never reach 2, go to 3 and then to 2, or go to 3 and back to 1 and now the story starts over again. Use this observation to write and solve a simple equation for p.

 ii. Use the linear algebra ideas you learned in class.

 (f) Starting at 4, what is the expected time of first return to 4?

 (g) Starting at 4, what is the expected number of steps before you reach 5? Again, solve this in two ways:

 i. By direct inspection of how this could happen.

 ii. Using linear algebra.

 (h) What is the limit of P(Xn = 5|X0 = 1) as n → ∞?

 

Answer 1