A Jupyter Notebook Project To Automate Common Markov Chain Calculations
Made in collaboration with Tighe Clough
We wish to differentiate between different kinds of Markov Chains, including:
- Ergodic
- Regular
- Absorbing
Distinguishing ergodic Markov chains ended up being more complicated than the others. The approach we took was to consider the Markov chain as a directed graph, consisting of edges and nodes. We used a pared-down Tarjan's algorithm to check if the graph has more than one single strongly connected component (SCC). An SCC is a section of the graph where all nodes/states can reach each other. An ergodic transition matrix should have only 1 of these by definition. If the graph was found to have an SCC at a root node other than the first node searched, then we could determine that the graph has more than one SCC and classify it as non-ergodic.
General questions we could answer are:
- ✅ Probability to go from state a to state b in k steps
- ✅ Average number of times in a state before being absorbed
- ✅ Average number of steps before being absorbed
- ✅ Probability that we are absorbed by state b if we start in state a (be absorbed)
- ✅ Find the fixed vector of a matrix
- ✅ Mean First Passage Time of ergodic matrix
- ✅ Mean first return time for state a
In the current version, functions to answer each of these have been implemented and tested for correctness.
Our calculator works on right stochastic matrices as input (where the rows sum to 1), and not left stochastic matrices (where the columns sum to 1).
An equilibrium distribution can be thought of as a special eigenvector with eigenvalue 1 (wT = 1w). We found the fixed vectors through finding the vectors in the E1 space with non-negative components that sum to 1.
At the bottom of the notebook, a REPL (Read-Eval-Print-Loop) style calculator has been implemented. If this were to be developed furhter, we may decide to treat the functions as a separate project, instead opting to develop some API. Doing so would allow for use in other languages and mediums, such as an interactive website for example.