When I was a kid, I always yearned to be a prophet and predict everyone’s future. Seven-year-old me was obsessed with the potential idea of a formula for life, and if a person’s initial condition is known since birth, it might be possible to predict how they would end up. Thankfully such a formula doesn’t exist, otherwise, life would be boring and pointless.
I could never imagine that ten years after my daydream of being a life-teller, the idea of predicting the future state of a situation can be easily illustrated by one of my favorite applications of linear algebra: the Markov chain. To fully understand this concept and where it comes from, we need some basic linear algebra, and I will assume you have background knowledge of matrix equations. A Markov chain is a powerful tool applied in natural sciences, data science, business, and sociology to predict events in correlation with multiple variables, in which the current state is determined by the previous state, and the transition rate between two adjacent states is constant.
Let’s imagine three islands: A, B, and C. There are 1000 birds on each island in year 0. Each year, ⅓ of the birds in A are migrating to B, and ⅓ are migrating to C. Similarly, ⅓ birds in B are migrating to A and ⅓ to C. Lastly, ½ of C’s birds are migrating to A and ½ to B, so none of the C birds would be on C the next year.
We can use this graph to illustrate the situation:
Figure 1. Illustration of the island example
We can use A(n), B(n), C(n) to describe the population in year n on islands A, B, and C in year n, respectively. To integrate the data we use a vector P(n) to represent the overall population status in year n:
Looking at island A, in the next year (n+1), there will be ⅓ birds from A, ⅓ birds migrated from B, and ½ migrated from C from year n. Thus we can find a way to express A(n+1) in terms of A(n), B(n), C(n):
A(n+1) = ⅓A(n) + ⅓B(n) + ½C(n)
Apply a similar operation to islands B and C, we have:
B(n+1) = ⅓A(n) + ⅓B(n) + ½C(n)
C(n+1) = ⅓A(n) + ⅓B(n) + 0C(n)
Therefore,
The matrix below is called a Markov matrix. It describes the function applied to state n to reach state (n+1). Let’s call it M.
The columns of this matrix have a sum of one since they represent how the percentage of A’s population is re-distributed within one year, and the total population of these birds stays the same.
Similarly to P(n+1),
So we can conclude that
P(n) = MⁿP(0)
Let’s see what will happen after 1, 10, and 50 years:
P(1) = MP(0)
P(5) = MP⁵(0)
P(50) = M⁵⁰P(0)
With
Therefore,
Before actually computing the vector, let’s observe the matrices M, M⁵, M⁵⁰. You may notice that the first two and the third columns of M do not look alike at all, but they gradually converge to the same vector as time passes by (as n increases). Finally, the three columns of M⁵⁰ become identical.
What does this mean? We know the first row represents the population on island A, more specifically, the (1,1) entry is the percentage of birds who start with A and end with A, the (1,2) entry is the percentage of birds who start with B and end with A, and the (1,3) entry is the percentage of birds who start with C and end with A. It’s the same for the second and third rows. Since the percentages described above are the same, 0.374999 of the total population will be in A after 50 years.
Let’s see how the same logic works for all islands through algebraic computation:
Because the columns of M⁵⁰ are the same, we can simplify the answer by combining the same factors 0.374999, 0.374999, and 0.249999.
Hence,
It means the population on the three islands would reach an equilibrium as the same migration pattern operates for a long time. Islands A and B will have 0.374999 of the total population, and island C will have 0.249999 of the total population. The percentage of the population distributed on each island is independent of the initial population because the percentages are the same. However, the actual population of each island is correlated to the initial total population.
The same logic of using matrix functions to solve a sequence of events in which the possibility of each event only depends on the state of the previous event, called a Markov chain, can be applied to the prediction of population growth and customer behavior (Wikipedia Contributors, 2024). We have to be careful to note that the Markov matrix does not necessarily stabilize as in the bird example. Even if it does stabilize, the columns will not necessarily be the same. These different results correspond to different situations.
*Special thanks to the Stanford Math51 course
Work Cited
Wikipedia Contributors (2024). Markov chain. [online] Wikipedia. Available at: https://en.wikipedia.org/wiki/Markov_chain [Accessed 28 Jul. 2024].
댓글