Introduction to Markov chain : simplified! (with Implementation in R)

Tavish Srivastava 25 Jun, 2020 • 4 min read

Markov chain is a simple concept which can explain most complicated real time processes.Speech recognition, Text identifiers, Path recognition and many other Artificial intelligence tools use this simple principle called Markov chain in some form. In this article we will illustrate how easy it is to understand this concept  and will implement it in R.Introduction to Markov chain simplified

 

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 probability easy and enables this algorithm to be applied in number of scenarios. In this article we will restrict ourself to simple Markov chain. In real life problems we generally use Latent Markov model, which is a much evolved version of Markov chain. We will also talk about a simple application of Markov chain in the next article.

[stextbox id=”section”] A simple business case [/stextbox]

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:

[stextbox id=”grey”]

P(P->P) : Probability of a customer staying with the brand Pepsi over a month = 0.7

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

P(C->C) : Probability of a customer staying with the brand Coke over a month = 0.9

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

[/stextbox]

We can clearly see customer tend to stick with Coke but Coke currently has a lower wallet share. Hence, we cannot be sure on the recommendation without making some transition calculations.

[stextbox id=”section”] Transition diagram [/stextbox]

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

transition

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(P->P) + Current market Share of Coke * P(C->P)

Market share (t+1) of Coke = Current market Share of Coke * P(C->C) + Current market Share of Pepsi * P(P->C)

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

Current State X Transition Matrix = Final State

trans1

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.

trans2

[stextbox id=”section”] Steady state Calculations [/stextbox]

Furthermore to the business case in hand, the soda company wants to size the gap in market share of the company Coke and Pepsi in a long run. This will help them frame the right costing strategy while pitching to Coke.The share of Pepsi will keep on going down till a point the number of customer leaving Pepsi and number of customers adapting Pepsi is same. Hence, we need to satisfy following conditions to find the steady state proportions:

Pepsi MS * 30% = Coke MS * 10%  ……………………………………………..1

Pepsi MS + Coke MS = 100% ……………………………………………………2

4 * Pepsi MS = 100% => Pepsi MS = 25% and Coke MS = 75%

Let’s formulate an algorithm to find the steady state. After steady state, multiplication of Initial state with transition matrix will give initial state itself. Hence, the matrix which can satisfy following condition will be the final proportions:

Initial state X Transition Matrix = Initial state

By solving for above equation, we can find the steady state matrix. The solution will be same as [25%,75%].

Now let’s solve the above example in R.

Implementation in R

 

Step 1: Creating a tranition matrix and Discrete time Markov Chain

 

Output

trans_mat
[,1] [,2]
[1,] 0.7 0.3
[2,] 0.1 0.9


#create the Discrete Time Markov Chain
MC 1 
A 2 - dimensional discrete Markov Chain defined by the following states: 
Pepsi, Coke 
The transition matrix (by rows) is defined as follows: 
Pepsi Coke
Pepsi 0.7 0.3
Coke 0.1 0.9

Plot

Step 2: Calculating the Market Share after 1 Month and 2 Months

Output

#Market Share after one month

Pepsi Coke
0.43 0.57

#Market Share after two month

Pepsi Coke
0.358 0.642

Step 3: Creating a steady state Matrix

Output

Pepsi Coke
0.25 0.75

 

[stextbox id=”section”] End Notes  [/stextbox]

In this article we introduced you to Markov chain equations, terminology and its implementation in R. We also looked at how simple equations can be scaled using Matrix multiplication. We will use these terminologies and framework to solve a real life example in the next article. We will also introduce you to concepts like absorbing node and Regular Markov Chain to solve the example.

Did you find the article useful? Did this article solve any of your existing problems? Have you used simple Markov chain before? If you did, share with us your thoughts on the topic.

If you like what you just read & want to continue your analytics learning, subscribe to our emails, follow us on twitter or like our facebook page.

Tavish Srivastava 25 Jun 2020

Tavish Srivastava, co-founder and Chief Strategy Officer of Analytics Vidhya, is an IIT Madras graduate and a passionate data-science professional with 8+ years of diverse experience in markets including the US, India and Singapore, domains including Digital Acquisitions, Customer Servicing and Customer Management, and industry including Retail Banking, Credit Cards and Insurance. He is fascinated by the idea of artificial intelligence inspired by human intelligence and enjoys every discussion, theory or even movie related to this idea.

Frequently Asked Questions

Lorem ipsum dolor sit amet, consectetur adipiscing elit,

Responses From Readers

Clear

Youssef MOURACHE
Youssef MOURACHE 19 Jul, 2014

I found this Web Site very interesting, i would like receive new posts by email.

sag
sag 22 Jul, 2014

ok

nishant
nishant 23 Jul, 2014

Very interesting, informative and to the point

swadheen Jain
swadheen Jain 24 Jul, 2014

Very Interesting yet the simplest way you explain the concept.

Ravi Kamani
Ravi Kamani 30 Jul, 2014

Hi Tavish,Very nice article,even a first timer can understand the concept clearly.

Anchal
Anchal 03 Sep, 2014

Quite informative. Looking forward to read next article on a real life example.

Vaishali
Vaishali 03 Jan, 2015

Very informative Blog! Thanks for sharing! A Markov chain is a stochastic process with the Markov property. The term "Markov chain" refers to the sequence of random variables such a process moves through, with the Markov property defining serial dependence only between adjacent periods (as in a "chain"). It can thus be used for describing systems that follow a chain of linked events, where what happens next depends only on the current state of the system. In literature, different Markov processes are designated as "Markov chains". Usually however, the term is reserved for a process with a discrete set of times (i.e. a discrete-time Markov chain (DTMC)). Although some authors use the same terminology to refer to a continuous-time Markov chain without explicit mention.

manik
manik 21 Aug, 2015

what a wonderful explanation of markov chain.

Sanjay Singh
Sanjay Singh 11 Dec, 2016

Well written and explained. Very simple to understand. Nice examples. Thanks!!!

Aditya
Aditya 12 Dec, 2016

The best explanation of Markov chain . Salute to you !

Deepa Athimoolam
Deepa Athimoolam 06 Jun, 2017

It is a good explanation. Have a question regarding probability, Theory, am able to understand and which data should be used for this? The probability of staying with a brand and switching to new brand ,how is it calculated and which data can be used for this calculation?

B s kambo
B s kambo 10 Oct, 2017

Concept illustrated in examples are excellent. Though I have no knowledge of mc. But the way u tell in the said examples clarified the concept..I am senior citizen above seventy but has strong desire to learn this mc. Ćan u suggest some reference for person like me to learn self.What level of mathematics is need to study mc.I am graduate in math 45 years back from Delhi university.

  • [tta_listen_btn class="listen"]