Question

Can i please have a quick explanation on Markov Chain in linear algebra.

Thanks

Answer 1

Markov Chain

Markov chain is a simple concept which can explain most complicated real time process. Speech recognition, text identifiers, Path recognition and many other artificial intelligence tools use this simple principle called Markov chain in some form.

Markov chain is based on a principle of 'memorylessness'. In other words the next state of the process only depends on the previous state and not the sequence of states. This simple assumption makes the calculation of conditional probabilityeasy and enables this algorithm to be applied in number of scenarios. Now we will see a simple application of Markov chain below.

Application of Markov chain :

Coke and Pepsi are the only companies in country X. A soda company wants to tie up with one of these competitor. They hire a market research company to find which of the brand will have a higher market share after 1 month. Currently, Pepsi owns 55% and Coke owns 45% of market share. Following are the conclusions drawn out by the market research company.

P(PP) : Probability of a customer staying with the brand Pepsi Over a month = 0.7

P(PC) : Probability of a customer switching from Pepsi to Coke over a month = 0.3

P(CC) : Probability of a customer staying with the brand Coke Over a month = 0.9

P(CP) : Probability of a customer switching from Coke to Pepsi over a month = 0.1

The four statements made by the research company can be structured in a simple transition diagram.

The diagram simply shows the transitions and the current market share. Now, if we want to calculate the market share after a month, we need to do following calculations :

Market share (t+1) of Pepsi = Current market share of Pepsi * P(PP) + Current market share of Coke * P(CP)

Market share (t+1) of Pepsi = Current market share of Coke * P(CC) + Current market share of Pepsi * P(PC)

This calculations can be simply done by looking at the following matrix multiplication :

Current state X Transition matrix = Final state

As we can see clearly see that Pepsi, although has a higher market share now, will have a lower market share after one month. This simple calculation is called Markov chain. If the transition matrix does not change with time, we can predict the market share at any future time point. Let's make the same calculation for 2 months later.