Markov Matrices

Markov Matrices  - Applications

Before going into the applications, let’s first discuss what is a Markov chain? 

 In simple terms, its a mathematical system with finite number of states where the system can be in only one of the possible states at any given time and the probability of the system being in a state at time period n depends only on its state at n-1 time period.  

Lets take an example: 

In a country, population of urban areas is 100 mm and that of rural areas is 200 mm. Every year, 10 % of the urban population moves to rural areas and 40 % of the rural population moves to urban areas. Now, the government of the country is interested in finding the population of rural and urban areas after 1 year, 10 years, and after too many years (tending to infinity), if the above percentages remain same and  everything else is constant.

We solve this problem with Markov matrix. It’s a very basic problem since there are only 2 states. One will appreciate power of Markov process when applied to problems with more than 2 states (for next time).

We put all the percentages (probability distribution) in a matrix as follows :

  A  =    U                 R

     U   (  0.90             0.40)

     R   (  0.10              0.60)

It means 90% of the urban population at time period T0 remains urban and rest 10 % moves to rural areas, same for second column. The above matrix A is called a Transition(Markov) matrix, one important property of Markov matrix is sum of values in a column is always 1, also all values in Markov matrix are >=0 as they are probabilities.

We know the initial distribution of population, at time period 0,  we put them in a vector :

 P0 = ( 100 )

          ( 200 )

Now, if we have to find  urban population after 1 year , it is simply (0.90)*100 + (0.40)*200 =  170.

And rural population will be (0.10)*100 + (0.60)*200 =130.

Or P1 =    
     (  0.90   0.40 )    ( 100 )     =    ( 170 )   

      ( 0.10   0.60 )    ( 200 )            ( 130 )

i.e. P1 = A*P0

Now, Population after 2 years,  P2 = A*P1  ….. as population in any given state depends only on its previous state.

So, P2 = A*P1 = A*(A*P0) = (A^2) *P0

Likewise, population after 10 years, P10 = (A^10) * P0

To make calculations simple, we decompose our matrix , we convert matrix A to UDU¯¹ where U is a matrix of which the columns correspond to Eigen vectors of A, D is a diagonal matrix with values on the diagonal as Eigen values of A.  

(Matrix decomposition ; http://mathworld.wolfram.com/MatrixDiagonalization.html )

Another property of Markov Matrix : One of the eigen values of a Markov matrix is 1 (more on this and what are eigen values/eigen vectors for next time ).

For eigen value 1, we find corresponding eigen vector.

Here comes our famous eigen value – eigen vector equation,

  As=ƛs  …….. (1)

where ƛ is an eigen value of matrix A and s is the eigen vector corresponding to eigen value ƛ.  

If we substitute ƛ = 1 in above equation, one of the eigen vectors,
 s =  ( 4 )
        ( 1 )
  

Since, As=ƛs ....  As-ƛs=0  …….. (A-ƛI)s = 0 …… I is the identity matrix.

For the characteristic polynomial, determinant (A-ƛI) = 0 ……. Solving this characteristic polynomial we get the other eigen value as ½ .

Putting ƛ = ½ in our equation (1), we get eigen vector as  ( 1 )
                                                                                      ( -1 )

Thus,  A = UDU¯¹  = (  4   1 )    ( 1   0 )  ( 1/5    1/5 )

                                ( 1  -1 )    ( 0   ½ ) ( 1/5    -4/5 )

A^10 = U*(D^10)* U¯¹

(For inverse of matrix, http://www.mathwords.com/i/inverse_of_a_matrix.htm )

Population after 10 years, P10 = (A^10) * S = U*(D^10)* U¯¹ * S

P10 =   (  4   1 )   ( 1   0       )     ( 1/5    1/5      100 )

            ( 1  -1 )   ( 0   ½^10 )     ( 1/5    -4/5     200 )

       =  ( 240 – 140/(2^10)   )

           ( 60  + 140/(2^10)   )

Population after too many(infinite) years, P(inf) = (A^inf) * S = U*(D^inf)* U¯¹ * S

P(inf) =     ( 4   1 )     ( 1   0 )          ( 1/5    1/5 )     (  100 )

                ( 1  -1 )    ( 0   0 )         ( 1/5    -4/5 )    (  200 )

Solving above, we get P(inf) =    ( 240 )

                                                  ( 60   )

This means, if the probability distribution and everything else remains same,after too many years, the population in urban areas would be 240 mm and that in rural areas would be 60 mm, which gives us a very significant insight into the population of the country which otherwise would not be known, and it could be a concern for urban areas in future. 

  

In the same way, we can solve following problem also,

Consider population of three countries , india(100), china(200), usa (600).

Every year, 10% of Indian population moves to usa, 5 % moves to china. 20% of china population moves to usa and 5% of its population moves to india. 5% of usa population moves to india and 5% to china.

Lets say the government of these countries is interested in finding population of their countries after few years if it keeps on happening like this, everything else remaining same .

We will discuss above problem and few more problems next time (sry for matrix notations , im still figuring out how to put matrix brackets on blogspot :|).

If any mistake in above calculations or anything unclear, leave a comment or shoot an email puneetgoenka24@gmail.com