Introduction
In my previous articles, we have been gaining an intuition of Markov Chains. In a nutshell, a Markov Chain is a random process that evolves in discrete time in a discrete state space where the probability of transitioning between states only depends on the current state. The system is completely memoryless. To gain a full understanding of the previous sentences, please refer to my former articles here:
Markov Chains Simply Explained
In this article, we will discuss some common characteristics and properties of Markov Chains!
Irreducibility
A Markov Chain is said to be irreducible, if it is possible to transition from any given state to another state in some given time-step. All states communicate with each other. Mathematically, there exists some time-step t > 0 where:
Which is the probability P of transitioning from state i to state j in some given time step t.
The following Markov Chain is irreducible as we can go from any state to any other state in the system:
Absorbing States and Periodicity
A state is defined to be absorbing, if when you reach that state, you cannot leave it. In other words, it has a 100% probability of transitioning to itself.
An absorbing state is said to have a period of 1, as we know for every subsequent time-step we will end up back at that same state. A state with period of 1 is also known to be aperiodic and if all the states are aperiodic, then the Markov Chain is aperiodic.
Note: The self-transition probability doesn’t necessary need to be 1 to be aperiodic. It just needs to be greater than 0. Therefore, all absorbing states are aperiodic but not all aperiodic states are absorbing states.
In general, the period of a state i is the greatest common denominator of all integers for t > 0:
For example, for the following Markov Chain below each state has a period of 3. This is because, for example, once we leave state A at t = 0, we arrive back at A at t = 3. Furthermore, as every state is periodic, the Markov Chain is periodic with a period of 3.
Transient and Recurrent States
A given state i is considered to be transient if upon entering that state, there is a positive probability that the chain may never return to state i ever again.
A recurrent state is basically one that is not transient. So, there is a probability of 1 when entering state i, the chain will definitely return to that given state an infinite number of times (provided we are taking infinite time steps).
Consider the following Markov Chain:
We can see that states A and B are transient as there is a probability when leaving these two states we can end up at states C or D which only communicate with each other. Therefore, we will never get back to states A or B as the Markov Chain will cycle through C and D.
On the other hand, states C and D are recurrent as when we leave C, we know we will be back there in two time-steps (therefore it has a period of 2!).
Conclusion
Hope you enjoyed this article! This one was on the shorter side, but is useful to further build our intuition of Markov Chains and the different types that exist. In the next article, we will discuss Hidden Markov Chains!
Another Thing!
I have a free newsletter, Dishing the Data, where I share weekly tips for becoming a better Data Scientist. There is no "fluff" or "clickbait," just pure actionable insights from a practicing Data Scientist.
