Applications to Markov Chains

The Markov chains described in this section are used as mathematical models of a wide variety of situations in biology, business, chemistry, engineering, physics, and elsewhere. In each case, the model is used to describe an experiment or measurement that is preformed many times in the same way, where the outcome of the trial of the experiment will be one of several specified possible outcomes, and where the outcome of one trial depends only on the immediately preceding trial.

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. A Markov chain is a sequence of probability vectors x0, x1, x2,.... together with a stochastic matrix P, such that x1=Px0, x2=Px1....Then the Markov chain described by the first order difference equation xi+1=Pxk for k=0,1,2.....

When a Markov chain of vectors in R^n describes a system or a sequence of experiments, the entries in xk, the probabilities that the system is in each of n possible states, or the probabilities that the outcome of the experiment is one of n possible outcomes. For this reason, xk is often called a state vector.

Example One: Examine a model for population movement between a city and its suburbs. The annual migration between these two parts of the metropolitan region was governed by the migration matrix M.

From: 

City Suburbs      

M = [.95        .03 ]                

[.05        .97 ]       

That is each year 5% of the population moved to the suburbs, and 3% of the suburban population moves to the city. The columns of M are probability vectors, so M is a stochastic matrix. Suppose the 2014 population of the region is 600,000 in the city and 400,000 in the suburbs. Then the initial distribution population in the region is given by x0. What is the distribution population in 2015? in 2016? 

After one year, the population vector 

[600,000

400,000]

changed to 

[.95    .03  x  600,000] = [582,000]

[.05    .97  x  400,000] = [418,000]

If we divide by both sides of the this equation by the total population of 1 million, and use the fact that kMx= M(kx), we find that 

[.95  .03  x .600 = [.582]

[.05  .97  x .400 = [.418]

The vector x1 = [.582

                           .418]

gives the population distribution in 2015. that is 58.2% of the region lived in the city and 41.8% lived in the suburbs. Similarly the population distribution in 2016 is described by a vector x2, where

x2 = Mx1 = [.95  .03  x  .582] = [.565]

                     [.05  .97  x .418]   =[.435]

gives the population distribution in 2016, that is 56.5% of the region lived in the city and 43.5% lived in the suburbs. 

If P is a stochastic matrix, then the steady-state vector (or equilibrium vector) for P is a probability vector q such that pq=q it can be shown that every stochastic matrix has a steady-state vector. 

Example two: The probability vector q = [.375

                                                               .625] is a steady state vector for the population migration matrix M, because 

Mq = [.95  .03  x  .375] = [.35625 + .01875] = [.375] q

          [.05  .97  x  .625] = [.01875 + .60625] = [.625] q

If the total populaiton in example one, is 1 million, then q in this example would correspond to having 375,000 persons in the city and 625,000 in the suburbs. At the end of one year, the migration out of the city would be (.05)(375,000) = 18,750 persons, and the migration into the city from the suburbs would be (0.3)(625,000) = 18,750 persons. As a result, the populaiton in the city would remain the same. Similarly, the suburban populaiton would be stable. 

Theorem 18: If P is an mxn regular stochastic matrix, then P has a unique steady-state vector q. Further, xo is any initial state and xk+1 = Pxk, for k = 0,1,2,....then the Markov chain {xk} converges to q as k goes to infinity. 

Examine Problem: On any given day a student is either healthy or ill. Of the students who are healthy today, 95% will be healthy tomorrow. Of the students who are ill today, 55% will still be ill tomorrow. 

a.) What is the stochastic matrix for this situation?

b.) Suppose 20% of the students are ill on Monday. What faction or percentage of the students are likely to be ill on Tuesday or Wednesday? 

c.) If a student is well today, what is the probability that he or she will be well two days from now? 

Solving matrixes using cofactor expansion:

Co-factor Expansion: 

Formula: Given A= [aij], the (i, j) cofactor of A is the number Cij given by Cij=(-1)^(i+j) det Aij

then det A= a11C11+a12C12+......+a1nC1n. This formula is called a cofactor expansion across the first row of A. 

Theorem One: The determinant of an m x n matrix A can by computed by a cofactor expansion across any row or down any column. The expansion across the ith row using the cofactors in the above equation is det A = a11C11+a12C12+....+a1nC1n. The cofactor expansion down the jth column is det A= a1jC1j+a2jC2j+.....+anjCnj. 

The plus or minus sign is the (i,j)-cofactor depends on the position of a1j in the matrix, regardless of the sign of a1j itself. The factor (-1)^(i+j) determines the following checkerboard pattern of signs: 

Example One: Use a cofactor expansion to solve the matrix. 

Theorem One is helpful for computing the determinant of a matrix that contains many zeros. For example, if a row is mostly zeros, then the cofactor expansion across that row has many terms that are zero, and the cofactors in those terms need not to be calculated. The same approach works with a column that contains many zeros. 

Examples: Find the cofactor expansion for each matrix. 

Theorem Two: If A is a triangular matrix, then det A is the product of the entries on the main diagonal of A. 

Example: Find the cofactor expansion

Note: Today's standards, a 25 x 25 matrix is small. Yet it would be impossible to calculate a 25 x 25 determinant by cofactor expansion. In general, a cofactor expansion requires more than n! multiplications, and 25! is approximately 1.5 x 10^25. If a computer performs one trillion multiplications per second, it would have to run for more than 500,000 years to compute a 25 x 25 determinant by this method. 

Examine Problem: Find the cofactor expansion and the determinant of the following matrix equation.