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.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.
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
