Part IV. Application to Markov Chains

In this exercise, you will work with Markov Chains. Please read the theoretical part and perform the tasks presented below.

Theory: A vector with nonnegative entries that add up to 1 is called a probability vector. A stochastic matrix is a square matrix whose columns are probability vectors (this corresponds to the definition of a left-stochastic matrix in an early project). A Markov chain is a sequence of probability vectors , together with a stochastic matrix P, such that,

.

In other words, a Markov chain is described by the first-order difference equation for

The n entries of a vector list, respectively, a probability that the system is in one of the n possible states. For this reason, is called a state vector.

If P is a stochastic matrix, then a steady-state vector for P is a probability vector q such that .

A stochastic matrix P is called regular if some matrix power contains only strictly positive entries.

Theorem: If P is an regular stochastic matrix, then P has a unique steady-state vector q. Further, if is any initial state and for , then the Markov chain converges to q as .

Note: The steady-state vector describes the state of the dynamical system in a long run, and the initial state has no effect on the long-term behavior of the Markov chain.

(Read more on Markov Chains in the textbook: Section 4.9, Applications to Markov Chains.)

Exercise 6 (4 points) Difficulty: Moderate

**Create a function in MATLAB

function q = ststate(P,x0)

[~,n]=size(P);

S=sum(P);

The function has to perform the following tasks:

** Check if the given matrix P is stochastic by using closetozeroroundoff(S-ones(1,n)).

If P is not stochastic, the outputs are:

disp('Error: P is not stochastic')

q=[];

If P is stochastic, do the following:

**Find the steady-state vector q. Recall: the steady-state vector is the probability vector which is a solution of , or, equivalently, . A rational basis for the solution set of this system, which should contain here only one vector, can be found by

Q = null(P-eye(n),'r');

To get the unique (probability) vector q, you need to scale the vector , that is, , where (the sum of the entries of the column vector ).

**Verify that the Markov chain converges to q by calculating consecutive.

until, for the first time,

**Output xk and the number of iterations k.

Note on the form of the outputs:

You can compute xk by using while loop: initialize x1 and k, use the formula x1=P*x0, set up while loop, and reassign x0=x1 after each iteration. Doing it this way, you will need to output (which will be your xk after the loop terminates) and the number of iterations k (which you can find by setting a counter within the loop).

Please make sure that you suppress all intermediate iteration!

**Type the function ststate in your diary file.

**Run the function q = ststate(P,x0)on the following matrices P and vectors x0:

(a) P=[.3 .3;.5 .7], x0=[.4;.6]

(b) P=[.5 .3;.5 .7] and x0=[.4;.6] is the same as in part (a).

(c) P=[.9 .2;.1 .8] is a migration matrix between two regions and the initial vectors are:

x0=[.12;.88], x0=[.14;.86], and x0=[.86;.14]

% Compare the output vectors q in part (c) for different initial vectors and comment whether the initial vector has an impact on the steady-state vector q. What about the number of iterations k?

(d) Car rental pick-up/return matrix between the Airport, Downtown, and Metro, and

P=[.90 .60 .30; .05 .30 .40;.05 .10 .30], x0=[.6;.3;.1]

(e) The vector x0 is the same as in (d), but

P=[.90 .60 .30; .06 .30 .40;.05 .10 .30]

**Close out the diary file.