Life

We have seen how states move from one to another and the translation probabilities. It models a sequence in which the probability of the following (n+1) event depends only on the state of the previous (n) event. That is normal, Markov, where we can see the states. Imagine we can’t directly observe the states but only observe some indications. That is hidden Markov.

An often-used example is observing people’s attire and estimating if it’s sunny or rainy.

If it rains today, there is a 60% chance it will rain the next day and a 40% chance it will be sunny.
If it’s sunny today, there is a 70% chance it will be sunny tomorrow, and 30% will be rainy.

But you can’t observe that. All you see is people wearing a raincoat or normal clothes.
If it rains, there is a 60% chance you will see people wearing raincoats and 40% normal clothes.
If it’s sunny, there is a 90% chance you will see people wearing normal clothes and 10% rain clothes.

We have seen two ways of solving the end-stage distribution of cities in the example of Amy’s random walk to her friends. Method #1 is to multiply the transition matrix with itself n times and finally multiply with the initial-state distribution. Method #2 is to solve the equation, P X* = X*.

In the matrix form

0.0 0.33  0.0  0.25   0.0
0.5 0.00  0.5  0.25   0.0
0.0 0.33  0.0  0.25   0.0
0.5 0.33  0.5  0.00   1.0
0.0 0.0   0.0  0.25   0.0

There is a third method: find the first eigenvector of the transition matrix and normalise it (i.e., divide it with the sum of elements to make the total distribution 1). We will manage it using an R program that has an inbuilt function to calculate the higher vector.

pM <- matrix(c(0.0, 0.5,  0.0, 0.50, 0.0, 
               0.333, 0.0,  0.333, 0.333, 0.0,
               0.0, 0.5, 0.0, 0.5,  0.0,
               0.25, 0.25,  0.25, 0.0, 0.25,
               0.0, 0.0,  0.0, 1.0, 0.0), nrow = 5)

eigenvec <- eigen(pM)$vectors
first_eigenvec <- eigenvectors[,1]

first_eigenvec/sum(first_eigenvec)

0.16663714 0.25003386 0.16663714 0.33333681 0.08335504

Amy lives in city A and has friends in cities B, C, D, and E. The following scheme represents the direct bus connections to these cities. Every Monday, she takes a direct bus at random, reaches the town, and stays with her friend for a week. How many weeks would she have spent in each city that year if she had done this for a year?

The route map suggests that on a given week, Amy has the following probabilities
1) Equal chances from A to B or D (0.5, 0.5)
2) Equal chances from B to A, C, or D (0.33, 0.33, 33)
3) Equal chances from C to B, D (0.5, 0.5)
4) Equal chances from D to A, B, C or E (0.25, 0.25, 0.25, 0.25)
5) Can move from E to D (1.0)

In the matrix form

0.0 0.33  0.0  0.25   0.0
0.5 0.00  0.5  0.25   0.0
0.0 0.33  0.0  0.25   0.0
0.5 0.33  0.5  0.00   1.0
0.0 0.0   0.0  0.25   0.0

The required task is to find the stable end distribution of cities, which can be done using the relationship.

P X^* = X^*

The expansion of the above equation leads to the following linear relationship that we will solve analytically.

0A + 0.33B + 0C + 0.25D + 0E = A
0.5A + 0B + 0.5C + 0.25D + 0E = B
0A + 0.33B + 0C + 0.25D + 0E = C
0.5A + 0.33B + 0.5C + 0D + 1E = D
0A + 0B + 0C + 0.25D + 0E = E
A + B + C + D + E = 1

Substitute for A in the first equation and solve the set of 5 linear equations using the following R program.

A <- matrix(c( 0.0,   0.5,  0.0,   0.50,  0.0, 
               1.333, -1.0, 0.333, 0.333, 0.0, 
               1.0,   0.5,  -1.0,  0.5,   0.0,  
               1.25,  0.25, 0.25,  -1.0,  0.25, 
               1.0,   0.0,  0.0,   1.0,  -1.0), nrow = 5)
B <- c(1, 0, 0, 0, 0) 

solve(A, B)

0.16686465 0.25007815 0.16661457 0.33335417 0.08333854

Let’s take another example. For a particular website, 40% of visitors don’t return next time. Of the non-visitors, 10% turn up next time. What is the website’s end-state distribution? Let V represent the visitor and NV the non-visitor.

We know the property of the end state: the distribution at which P X^* = X^*. Let’s fill in the available data.

The columns must add up to 100% or 1.

Let’s now expand the equation and change percentage data to fractions.

0.6 V + 0.1 NV = V
0.4 V + 0.9 NV = NV

NV = 4 V
But we know V + NV must be 1
V + 4 V = 1
V = 1/5
NV = 4/5

20% will visit, and 80% won’t.

We have seen that the initial distribution of counts (or the proportion) reaches a stable state after a few generations.

In other words, the (n+1)^th and the n^th give the same result for the same given initial distribution and the probability matrix.

Let’s work out for n = 10. X₁₀ = P¹⁰ X₀

pM <- matrix(c(0.8, 0.1, 0.1, 0.2, 0.7, 0.1, 0.1, 0.3, 0.6), nrow = 3)
stage0 <- c(0.4, 0.24, 0.36)
stage10 <- pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%stage0 
stage10

       [,1]
[1,] 0.45
[2,] 0.35
[3,] 0.20

And then for n = 11. X₁₁ = P¹¹ X₀

pM <- matrix(c(0.8, 0.1, 0.1, 0.2, 0.7, 0.1, 0.1, 0.3, 0.6), nrow = 3)
stage0 <- c(0.4, 0.24, 0.36)
stage11 <-pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%pM%*%stage0  
stage11

     [,1]
[1,] 0.45
[2,] 0.35
[3,] 0.20

It would be interesting to see how the probability matrix is transformed as the number of stages progresses. Here is the original matrix (P), followed by (P¹⁰).

0.8  0.2  0.1
0.1  0.7  0.3
0.1  0.1  0.6       

0.45 0.45 0.45
0.35 0.35 0.35
0.20 0.20 0.20

Elements in each raw are similar in magnitude, which suggests why the end result after multiplying it with the original proportion is the same after each stage.

Another interesting fact is how X_n changes with the initial proportion, X₀. We use the following X₀ values. Note that the sum of the proportions must add to 1.

stagen %*% c(0.4, 0.24, 0.36)
stagen %*% c(0.3, 0.4, 0.3)
stagen %*% c(0.1, 0.1, 0.8)
stagen %*% c(0.1, 0.8, 0.1)

There is no prize for guessing – they all lead to the same X_n value!

0.45
0.35
0.20

Last time, we saw how the next stage is developed from the current stage using the probability matrix.

X₁ = P X₀

There is a reason why it is called the Markov chain. The system we have developed can now predict the stage after the next stage, i.e., X₂. Multiply the probability matrix with X₁.

X₂ = P X₁

Substituting for X1,
X₂ = P P X₀
X₂ = P² X₀
or in general
X_n = Pⁿ X₀

Let’s work out the stage after 10 moves and plot and see where A ends up.

In the last post, we started an example to demonstrate the objective of Markov processes.

The question is, what is the expected number of customers in shops A, B, and C in the following week?

The whole formulation is nothing but future state = present state x a probability matrix. The probability matrix, fundamental to making this translation, is developed from the diagram we created earlier.

The first row of the matrix are the probabilities: A to A, B to A and C to A
The second row: A to B, B to B and C to B
The third row: A to C, B to C and C to C

Perform the matrix multiplication between the two. Here are the R codes.

pM <- matrix(c(0.8, 0.1, 0.1, 0.2, 0.7, 0.1, 0.1, 0.3, 0.6), nrow = 3)
pM

    [,1] [,2] [,3]
[1,]  0.8  0.2  0.1
[2,]  0.1  0.7  0.3
[3,]  0.1  0.1  0.6

pM <- matrix(c(0.8, 0.1, 0.1, 0.2, 0.7, 0.1, 0.1, 0.3, 0.6), nrow = 3)
past <- c(0.4, 0.24, 0.36)
future <- pM%*%past
future

      [,1]
[1,] 0.404
[2,] 0.316
[3,] 0.280

What are Markov Chains: An Introduction: Michel van Biezen