Who needs a Graphing Calculator when you've got JavaScript?
In this article, I’ll be exploring applications of Markov Chains. I’ve built a calculator in JavaScript to demonstrate how this kind of stochastic process works. “Stochastic“ sounds fancy but it’s based on the Greek word “stochos“, which means “guess“. Markov Chains allow us to model a future state based on a number of transitions. Typically we start with an initial state matrix and a transition matrix, then we can use matrix multiplication to calculate a future state based on the number of transitions specified.
Before considering any particular example, lets take a step back and look at what’s special about this kind of state prediction. While Andrey Markov wasn’t the first person to study stochastic processes, at the beginning of the 20th century he was one of the first mathematicians to emphasize the property of “memorylessness“. To me this means that if we’ve got a valid transition matrix then we can determine a future state without explicit knowledge of all intermediate states. In other words, you can accurately predict a future state without calculating all of the states that lead up to it. The calculator that I’ve built does depend on intermediate states to predict a specific future state, but there are ways to obtain values of a future state without making these calculations.
By design, my calculator only handles a subset of regular Markov Chains. This is because I’ve chosen to focus on the stationary matrix obtained in the long run of a regular Markov Chain. I’m getting ahead of myself here, so lets consider a specific example. I feel like there are endless applications for Markov Chains. They can be used in analyzing the labour force, housing trends, insurance, genetics, and modes of transportation. Basically, if you can reduce some change in state to a probability then you can use Markov Chains to predict a future state. One of the more obvious applications is modelling market share. Personally, I’m more fond of ecology so I’m going to take a typical market share problem and give it an ecological application.
Imagine a water source in a natural area that’s subject to a blue-green algal bloom. If you live in southern Ontario you may have noticed that these blooms have become more prevalent in recent years. Because this kind of algae can produce toxins harmful to humans and animals, it’s best for people to avoid contact with any water source exhibiting such a bloom. Given that we know it’s possible for humans in this particular area to choose another water source (assuming they’re not all exhibiting toxic levels of an algal bloom), how long will it take to get a population to use an alternative water source instead?
If we can represent the initial state of our human population as either using the toxic water source or an alternative water source it could look like this:
| Toxic | Non-Toxic |
|---|---|
| [0.9 | 0.1] |
In other words, the initial state of our population shows that 90% is using the toxic water source and only 10% is using an alternative. As these blooms have been appearing more frequently over the past decade, we’ve been able to gather data for a transition probability matrix:
| Toxic | Non-Toxic | |
|---|---|---|
| Toxic | 0.2 | 0.8 |
| Non-Toxic | 0.4 | 0.6 |
This matrix tells us that only 20% of the population using the toxic water source will choose it again. The good news is that 80% chooses a non-toxic water source after starting out with the toxic water source. Unfortunately, 40% of those who start out using a non-toxic water source end up choosing the toxic water source. 60% of the population continues to choose the non-toxic water source.
OK, get ready for some math magic! This is my favourite thing about regular Markov Chains: they’re guaranteed to reach a stationary matrix. The question I have is, how many transition states will it take before the stationary matrix is reached? Before I built my handy-dandy JS calculator, I didn’t have a graphing calculator and there wasn’t much out there to help me obtain an answer to this question.
There is a calculator built by Hiroshi Fukada back in 2004 that’s quite useful. One advantage it has over my calculator is that you can enter multi-dimensional transition matrices (which is great!), but it doesn’t give me an answer to my question. Granted, this aspect of Markov Chains is often ignored: usually what we care about most is reaching a stationary matrix. We want to know the state that the transition matrix is tending towards in the long run. We don’t necessarily care about how long that run ends up being. On the other hand, when the consequences of the transition are dire (as in the case of our toxic water source) we want the long run to be as short as possible. That’s why I built my calculator to provide the number of states required to reach a stationary matrix.
I’d like to use my calculator to show you something cool about Markov Chains: the stationary matrix is reached after the same number of transitions, regardless of what the initial state is. In other words, everything depends on the transition probability matrix, P. You can find the stationary matrix by multiplying P by itself until there’s no more change in the result you get. This is essentially what my calculator does. When you have an initial state S0, you’ll find that you’ll reach the stationary matrix after the same number of state transitions as it takes when multiplying P by itself.
Lets return to our example. Given our transition probability matrix P, the stationary matrix reached at a certain point is:
[0.33 0.67]
When you multiply P by itself over and over again, you’ll discover its values converging towards 0.33 and 0.67. Given that our first state, S0 = [0.9 0.1], you’ll find that it will reach this stationary matrix at the same power of P. Even though we’re multiplying our initial state by a power of P, it takes the same power of P to reach that stationary matrix. Alright, enough explanation I’ll let my calculator show you what I mean. Here it is, already set up with our example in mind.
First you’ll see the transition probability matrix, and a button with the words, “Calculate stationary matrix!“. If you click that button with the default values of the matrix entered, then you’ll get this result:
STATIONARY = [0.33333333 0.66666667] reached at: P power 10
The next matrix you’ll see is our initial state, with an input below it that allows you to enter the future state you want to obtain values for. If you use this input (“Required State“) to enter 11, and press the button with the words “Calculate resulting matrix!“, you’ll get this result:
9 = [0.33333339 0.66666661] NOT STATIONARY
You can see that the values here are very close to our stationary matrix but they’re not quite there yet. It takes one more multiplication to reach the stationary matrix. If you enter 12 here, you’ll get this result:
10 = [0.3333333 0.6666667] stationary at state: 10
One more caveat before we continue with our example: precision matters! You’ll find that if you were to enter the same transition matrix into Fukada’s calculator, the stationary matrix is reached much quicker. This is because I’ve chosen to maintain greater precision with my calculator. As it turns out, the number of transitions required to reach a stationary matrix depends on the precision maintained in your calculations. For our example, what we want to do is reduce the number of transitions it takes to reach our stationary matrix (regardless of the precision maintained). Feel free to test this out in both Fukada’s calculator and mine to ensure that this reduction is made.
Why are we trying to reduce the number of transitions it takes to reach our stationary matrix? We want people to avoid our toxic water source as quickly as possible. How can we do this? Lets look at our original transition probability matrix again:
| Toxic | Non-Toxic | |
|---|---|---|
| Toxic | 0.2 | 0.8 |
| Non-Toxic | 0.4 | 0.6 |
Maybe there’s no room for improvement with that first row: 20% of our population will continue using the toxic water source no matter what. If we look at the second row, there could be a way to prevent those using the non-toxic water source from starting to use the toxic water source. We could create an information campaign that targets everyone using an alternative water source, so that they know to avoid the toxic water source. If we do that, we could achieve a transition probability matrix that looks like this:
| Toxic | Non-Toxic | |
|---|---|---|
| Toxic | 0.2 | 0.8 |
| Non-Toxic | 0.3 | 0.7 |
If we’re able to reduce the percentage of people who switch from a non-toxic to the toxic water source, then maybe this will help us reach our stationary matrix sooner. Lets test it out in a calculator. When I enter the above transition matrix and calculate the stationary matrix, I get this result:
STATIONARY = [0.2727273 0.7272727] reached at: P power 7
This is a great improvement! Not only are we reaching our stationary matrix sooner, the values in that matrix are better than what we had before. Only 27% of the population is using the toxic water source, instead of 33%. You might be wondering, is it possible to reduce that percentage even more? I suspect that it is. Now that you’ve got two Markov Chain calculators at your disposal, you can play around with them to see how to make further reductions.
You may have noticed that I’ve left out one really important detail: matrix multiplication. All of the above calculations depend on it. If you want to check things out the old-fashioned, manual way by doing the matrix multiplication yourself then look at the JavaScript file (called index.js) inside the function, “matrices2x2Multiplied“ to see how it’s done ;)
Until next time, happy holidays and try to stay away from toxic water sources!