Markov Chains

---

Let’s try to map the movement of Freelancer drivers in Dhaka. We can divide the area into three zones – North Dhaka, Middle Dhaka and South Dhaka.
The movement of drivers from one zone to another zone will depend only on their current zone. We’ve determined the following probabilities for the movement of a driver:

• Among the North Dhaka’s Freelancer drivers, 30% will remain in North Dhaka, 30% will move to Middle Dhaka, while the remaining 40% will go to South Dhaka.
• Of all the drivers in Middle Dhaka, 50% and 30% will move to North Dhaka and South Dhaka, respectively; 20% will remain in Middle Zone.
• In the South Dhaka, drivers have a 40% chance of moving to North Dhaka, 40% chance of staying in the South Dhaka; 20% drivers will move to Middle Dhaka.

Once a driver is in a particular zone, he can either move to the next zone or stay back in the same zone. His movement will be decided only by his current state and not the sequence of past states.
The state space in this example includes North Dhaka, South Dhaka and Middle Dhaka. It follows all the properties of Markov Chains because the current state has the power to predict the next stage.

> zone <- c("North","Middle","South")
> zoneTPM <- matrix(c(0.3,0.3,0.4,
+                     0.5,0.2,0.3,
+                     0.4,0.2,0.4), 
+                   nrow=3, byrow=T, dimnames = list(zone,zone))
> zoneTPM

       North Middle South
North    0.3    0.3   0.4
Middle   0.5    0.2   0.3
South    0.4    0.2   0.4

Using markovchain package

The package named “markovchain” can help us in implementing Markov Chains in R.

Install and load the package in R -

> # install.packages("markovchain")
> library(markovchain)

Now using create a Markov Chain object -

> driverzone <- new("markovchain",
+                   states = zone,
+                   transitionMatrix = zoneTPM,
+                   name = "Driver Movement")
> driverzone

Driver Movement 
 A  3 - dimensional discrete Markov Chain defined by the following states: 
 North, Middle, South 
 The transition matrix  (by rows)  is defined as follows: 
       North Middle South
North    0.3    0.3   0.4
Middle   0.5    0.2   0.3
South    0.4    0.2   0.4

Using diagram package

To plot the above transition matrix we can use R package, “diagram.” The “diagram” package has a function called plotmat() that can help us plot a state space diagram of the transition matrix in an easy-to-understand manner.

Install and load the package -

> # install.packages("diagram")
> library(diagram)

Now to plot the transition probability diagram -

> plotmat(A = zoneTPM,
+         box.type = "circle",          # shape of box
+         box.lwd = 1,                  # border density of box
+         relsize = 0.9,                # scaling factor for size of graph
+         cex.txt = 0.7,                # size of probabilities
+         lwd = 1,                      # border density of state to state arrows
+         lcol = "black",
+         box.col = "cornsilk1",
+         box.size = 0.1,               # size of box
+         box.prop = 0.6,               # height to width ratio of box
+         arr.length = 0.5, arr.width = 0.2,
+         self.cex = 0.5,                          # size of self probability box
+         self.shifty = -0.03, self.shiftx = 0.13, # location of self prob. box
+         # name = c("North Dhaka","Middle Dhaka","South Dhaka"),  # Optional
+         main = "Transition Diagram",
+         cex.main = 1.3                # relative size of main title
+         )

The above Markov Chain can be used to answer some of the future state questions.

---

Question: Assuming that a driver is currently in the North Zone, what is the probability that the driver will again be in the North Zone after two trips?

---

Get R Programming assignment help at www.homeworkhelponline.net.

---

Answer:

Manually: A driver can reach the North Zone again in his second trip in three different ways: 1. Staying in the same zone i.e. North Dhaka to North Dhaka Probability: P(N-N) = 0.30.3 = 0.09 2. Middle Dhaka to North Dhaka Probability: P(M-N) = 0.40.4 = 0.12 3. South Dhaka to North Dhaka Probability: P(S-N) = 0.5*0.4 = 0.2

Therefore, Probability of second trip to North = 0.09 + 0.12 + 0.20 = 0.41 (0.40 approximately)

Using Markov Chain in R:

> driverzone^2

Driver Movement^2 
 A  3 - dimensional discrete Markov Chain defined by the following states: 
 North, Middle, South 
 The transition matrix  (by rows)  is defined as follows: 
       North Middle South
North   0.40   0.23  0.37
Middle  0.37   0.25  0.38
South   0.38   0.24  0.38

This gives us the direct probability of a driver coming back to the North Zone after two trips.

The calculation can be done for subsequent trips as well. The probability of coming back to North Zone in 4th trip :

> driverzone^3

Driver Movement^3 
 A  3 - dimensional discrete Markov Chain defined by the following states: 
 North, Middle, South 
 The transition matrix  (by rows)  is defined as follows: 
       North Middle South
North  0.383  0.240 0.377
Middle 0.388  0.237 0.375
South  0.386  0.238 0.376

However if we increase n (No. of trips) the predictive power tends to go down, where the Markov Chain reaches an equilibrium called stationary state. In the above case, after 9 trips the state becomes stationary -

> driverzone^9

Driver Movement^9 
 A  3 - dimensional discrete Markov Chain defined by the following states: 
 North, Middle, South 
 The transition matrix  (by rows)  is defined as follows: 
           North    Middle     South
North  0.3853211 0.2385321 0.3761468
Middle 0.3853211 0.2385321 0.3761468
South  0.3853211 0.2385321 0.3761468

The stationary state can be calculated using some linear algebra methods; however, R has a direct function, steadyStates() -

> steadyStates(driverzone)

         North    Middle     South
[1,] 0.3853211 0.2385321 0.3761468

So we can say that, in the stationary state, a driver has a probability of 0.385 of ending up in the North Dhaka.

If there were 100 drivers in all and each completes 9 trips in a day, how many of them will end up in the Middle Dhaka?

> steadyStates(driverzone)*100

        North   Middle    South
[1,] 38.53211 23.85321 37.61468

So, around 38 drivers will end up in North Dhaka, 24 in the Middle Dhaka and 37 in the South Dhaka.

---

This is a replication of this article. Thanks to author CHAITANYA SAGAR.