State Termination Probabilities in an Absorbing Markov Chain
Below is a succinct function
solve that takes an absorbing Markov chain represented as a list of lists and returns
a list of integers, one integer for each state, expressing the relative likelihood of terminating at that state.
Each state is represented as a row in the matrix. This row expresses the relative likelihoods of transitioning to each of the other states from this row. For example
[1, 0, 0, 0, 2] would mean we have a chance (33%) of transitioning to state 1 and a chance (66%) of transitioning to state 5.
To input a Markov chain edit the
chain variable, keep in mind to stick to the conventions:
- The first row is the start state
- Have at least one terminal state
- A terminal state can be written as a row of all zeros, or a row that has only a one in the column the same as the rows index. Example: A row five with all zeros and only a one in the fifth column would be a correct way to represent that state 5 in the absorbing Markov chain is a terminating state.
The solution is based around the idea that we can look at each pair of rows and reduce their function with regards to how they affect the probability of terminating at each state into one of the rows. There is no need for inverting or rearranging a matrix so it is an easy solution to code, the only function used that might not be considered a primitive in most languages is
gcd for getting the greatest common divisor, but in most cases it is available and if not it is easily coded in a few extra lines.
Running this Haskell code gives
Which tells us there is no chance of terminating at state 1, 2, or 4 because 0 was returned in the position that maps to those states, this is correct because these are transient states. And there is a chance (20%) of terminating at state 3, and a chance (80%) of terminating at state 5.