Wednesday, February 12, 2014

Markov Chain : Concept and application

It is a stochastic process used to model random progression of a system mathematically. Stochastic process is a process which is used to describe behavior of a random variable (system) over the time. Random progression refers to transition between states which are part of the system we are studying.

Consider a sequence of two states A and A' as ...AA'A'AA'AAA'A... in which the transition between A and A' can be captured by following matrix,


There are two important things in the screenshot above,
  • On left side we can see the transition diagram between A and A' where the probabilities are shown for each possible transition. Note that sum all numbers associated with outgoing arrows for any state must be 1. For example in state A, sum of 0.9 and 0.1 is 1.00.
  • On right side the same transitions are captured by a transition probability matrix. Note that sum of any row here must be 1. For example, consider the row with current state as A' where sum of 0.7 and 0.3 is 1.00 as those are only possible transitions for A'.

Now lets take one example,

An automobile insurance company categorizes its customers at the time of policy renewal into two categories as high-risk and low-risk category. So at every moment a policy holder is either in high-risk or low-risk category. A policy is renewed every year. Based on company data,
  • A existing high-risk driver have 60% chance of being categorized as high-risk and 40% chance of being categorized as low-risk at the time of policy renewal.
  • A existing low-risk driver have 15% chance of being categorized as high-risk and 85% chance of being categorized as low-risk at the time of policy renewal.
Initially only 10% of policy holder are classified as high-risk customers. What will be the risk distribution of policy holders after 1 year from now?


To understand the given transitions refer the image below,


Lets build the transition probability matrix,


Now lets calculate the probability after 1 year,


As we can see, at first the distribution is 10% (high-risk) and 90% (low-risk). Then we use values from the transition matrix to calculate probabilities after 1 year.

If we observe closely it is nothing but matrix multiplication, of following two matrices

Initial state = [ 0.1  0.9 ]

Transition matrix =    0.6     0.4  
                                 0.15   0.85

Now the examples above gives us the idea how we can solve simple problems using Markov modelling.

In real world Markov chain applications can be found everywhere from finance, economics to biology, physics, chemistry, music and sports. If we consider just music industry, then it can be used for algorithmic music composition to build next pitch and rhythm or to choose songs while you are driving in car or comparing musical works.

Source and image credits:

Finite Math: One-step Markov Chains by Brandon Foltz

Markov Chains - Part 1  by patrickJMT

 

No comments:

Post a Comment